Same Tree

Examples

Input: p = [1,2,3], q = [1,2,3]
Output: true

Every node in the same position holds the same value.

Input: p = [1,2], q = [1,null,2]
Output: false

Both trees have a node valued 2, but in p it's a left child while in q it's a right child - the structures don't match.

Input: p = [1,2,1], q = [1,1,2]
Output: false

The structures match, but the values at the second and third positions are swapped between the two trees.

Constraints

• The number of nodes in both trees is in the range [0, 100].

• -10^4 <= Node.val <= 10^4

Approach

Two trees match exactly when: both roots are missing (both null - a match), or both roots exist with equal values and their left subtrees match each other and their right subtrees match each other. That's a clean recursive definition - compare the current pair of nodes, then recurse into the corresponding left and right children of each tree.

Solutions

Recursive DFS

Compare the two current nodes: if both are null, they match. If only one is null, or their values differ, they don't. Otherwise, recursively check that both left subtrees match and both right subtrees match.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isSameTree(p, q) {
  if (p === null && q === null) return true;
  if (p === null || q === null) return false;
  if (p.val !== q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Time: O(n) — where n is the number of nodes in the smaller tree · Space: O(h) — recursion stack depth, where h is the shorter tree's height

Iterative BFS

Walk both trees in lockstep using a queue of paired nodes. At each step, pop one pair, compare them, and push their children pairs (left-with-left, right-with-right) to check later.

function isSameTree(p, q) {
  const queue = [[p, q]];

  while (queue.length > 0) {
    const [nodeP, nodeQ] = queue.shift();

    if (nodeP === null && nodeQ === null) continue;
    if (nodeP === null || nodeQ === null) return false;
    if (nodeP.val !== nodeQ.val) return false;

    queue.push([nodeP.left, nodeQ.left]);
    queue.push([nodeP.right, nodeQ.right]);
  }

  return true;
}

Time: O(n) — where n is the number of nodes in the smaller tree · Space: O(n) — the queue can hold up to a whole level of node pairs