#105

Same Tree

easy

treedepth-first-searchbreadth-first-searchbinary-tree

Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding pair of nodes holds the same value.

Two empty trees are the same. Two trees differ if either their shape differs (a node present in one and absent in the other) or any matched pair of nodes disagrees in value.

Each tree is given as a level-order array where null marks a missing child: [1, 2, 3] is root 1 with children 2 and 3.

Example

Input: p = [1,2,3]213q = [1,2,3]213

Output: true

Constraints

The number of nodes in each tree is in the range [0, 100].
-10^4 <= Node.val <= 10^4

Intuition

Two trees are the same when they have identical shape and every corresponding pair of nodes holds the same value. The structure of the check mirrors the structure of a tree: compare the two roots, then recursively compare their left subtrees and their right subtrees.

function isSameTree(p, q) {
  // Preorder serialization with '#' for nulls captures both value and shape.
  const encode = (node) =>
    node ? `${node.val},${encode(node.left)},${encode(node.right)}` : '#';
  return encode(p) === encode(q);
}

Brute force — serialize both trees (with null markers) and compare the strings: O(n) time and space.

That's correct, but it builds two full strings before comparing a single character — and it can't stop early when the trees differ at the very first node. Can we do better?

The key observation: compare the two trees in lockstep and short-circuit. At each step, both nodes null means this branch matches; exactly one null means the shapes differ; otherwise the values must match and both child-pairs must match recursively. The first disagreement returns false immediately.

Tracing p = [1, 2, 3] against q = [1, 2, 3]:

Roots: both 1 — equal, recurse on both child-pairs.
Left pair: both 2, and both their children are null-pairs → match.
Right pair: both 3, likewise → match. Every pair agrees, so the trees are the same.

Against q = [1, 2, null] the right pair would be 3 vs null — one present, one absent — returning false at that step without touching the rest.

The base cases do the shape check: both-null matches, exactly-one-null is an immediate mismatch.
This is the structural cousin of Symmetric Tree, which compares one tree against its own mirror by crossing the child comparisons; here the comparisons are straight (left-with-left, right-with-right).
No lane — the comparison descends two trees together, which a single scanned row can't show.

Optimization

Parallel recursion

Walk both trees in lockstep. If both nodes are null the (sub)trees match; if exactly one is null, or the values differ, they don't. Otherwise recurse on the left pair and the right pair and require both to match.

O(n) time, O(h) recursion space.

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

Complexity analysis

Time complexity: O(n). Here's why:

The lockstep recursion compares each pair of corresponding nodes once.

So O(n) (n = the size of the smaller tree at most), short-circuiting on the first mismatch.

Space complexity: O(h). Here's why:

Only the recursion stack — depth equal to the tree height h.

O(log n) balanced, O(n) worst case. No serialization strings are built.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
p = []nullq = []null	true	Two empty trees are the same.
p = [9]9q = []null	false	One node vs none — shapes differ.
p = [7,8,9]879q = [7,8,9]879	true	Identical shape and values.
p = [5,6]65q = [5,null,6]56	false	Same values, different shape (left vs right child).
p = [4,5,4]544q = [4,4,5]445	false	Same shape, mismatched values.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor