Same Tree — Solution

Problem

Given the roots of two binary trees, determine whether the trees are identical. To be identical, the trees must have the same shape and the same value at every corresponding position — two trees that differ at even one node (either by value or by one having a child where the other does not) are considered different.

Example — both trees are identical:

[1,2,3]

• Input: p = [1,2,3], q = [1,2,3]
• Output: true
• Explanation: Both trees have root 1, left child 2, and right child 3.

Counter-example — same values, different structure:

p:

[1,2]

q:

[1,null,2]

• Input: p = [1,2], q = [1,null,2]
• Output: false
• Explanation: p places 2 as a left child; q places 2 as a right child — same values, different shape.

Intuition

Two trees are the same only if they agree at every node simultaneously. Recursion maps naturally onto this: check the current pair of nodes, then delegate to the left pair and the right pair. Any mismatch at any depth immediately short-circuits to false, so no unnecessary work is done.

Solution — Recursive DFS

Compare both trees top-down. At each pair of nodes, three cases cover all possibilities: both null (equal), exactly one null (different), or both present (compare values then recurse).

1. If both nodes are null, return true — two empty positions are identical.
2. If exactly one node is null, return false — structures differ at this position.
3. If both values differ, return false.
4. Recurse on both left children.
5. Recurse on both right children and return true only if both subtrees match.

1def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
2    if p is None and q is None:
3        return True
4    if p is None or q is None:  # one is null, the other isn't
5        return False
6    if p.val != q.val:
7        return False
8    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time: O(n) — every node is visited exactly once, where n is the number of nodes in the smaller tree.
Space: O(h) — the recursion stack grows to the height of the tree; O(log n) for a balanced tree and O(n) in the worst case for a completely skewed tree.

Complexity Summary

Common Mistakes

• Returning false when both nodes are null — this is the successful base case: two empty positions are identical, so it must return true, not false.
• Dereferencing before null-checking — accessing .val on a null/None node causes a runtime error; the null checks must come first.
• Only comparing the current level's values — checking p.val == q.val without recursing into children cannot detect differences deeper in the tree.
• Using or instead of and on the recursive calls — both subtrees must match for the trees to be identical; or would return true as soon as one subtree matches, ignoring the other.
• Assuming same values implies same structure — [1,2,null] and [1,null,2] contain exactly the same values but are different trees; structure and values must both match.

Related Problems

• symmetric-tree — uses the same simultaneous two-pointer recursion, but compares a tree against its own mirror image instead of against a separate tree
• subtree-of-another-tree — calls same-tree comparison as a subroutine at every node to check whether one tree appears embedded in another
• leaf-similar-trees — compares two trees by collecting and comparing their leaf sequences, using the same DFS traversal pattern
• balanced-binary-tree — uses the same post-order DFS structure to propagate height information up from leaves to root
• invert-binary-tree — applies the same recursive decomposition to swap left and right children at every node