Same Tree (LeetCode 100)

The problem

You get the roots p and q of two binary trees. Return True if they are the same: identical shape, and equal values in every matching position. Otherwise return False.

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

    1         1
   / \       / \
  2   3     2   3

Output: True

Both roots are 1, both left children are 2, both right children are 3, and every child below that is empty in both trees.

A trickier case: p = [1, 2] and q = [1, null, 2] hold the same values but in different positions, so the answer is False.

How to think about it

Start with brute force. Serialise each tree to a list (say, level order with null markers) and compare the lists. It works, but it costs O(n) extra memory for both lists and you must get the null markers exactly right, or two different shapes can produce the same list.

The key insight: “same” is defined recursively. Two trees are the same if and only if the roots match, the left subtrees are the same, and the right subtrees are the same. That sentence is the algorithm. You just walk both trees in lockstep.

Get the base cases right; they carry the logic. If both nodes are empty, they match. If exactly one is empty, or the values differ, they don’t. Only when both exist and agree do you recurse.

Which pattern is this? Tree DFS, with two trees instead of one. The tell is a yes/no question about a whole tree that splits cleanly into the same question on subtrees.

Approach

1. If p and q are both None, return True.
2. If only one is None, or p.val != q.val, return False.
3. Otherwise return same(p.left, q.left) and same(p.right, q.right).

The and short-circuits, so the first mismatch stops the whole search.

Solution

def is_same_tree(p, q):
    if not p and not q: return True                          # both empty: match
    if not p or not q or p.val != q.val: return False        # shape or value differs
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
# is_same_tree(tree[1,2,3], tree[1,2,3]) -> True

Dry run

On the example, in the order the calls happen:

Complexity

• Time: O(n). Each pair of nodes is compared once, where n is the size of the smaller tree (the walk stops at the first difference).
• Space: O(h). The recursion goes as deep as the tree’s height: O(log n) if balanced, O(n) if skewed.

Edge cases and pitfalls

• Both trees empty returns True; one empty and one not returns False.
• Same values, different shape ([1,2] vs [1,null,2]) must be False. Comparing only in-order value lists gets this wrong.
• Check None before .val. Reading p.val when p is None raises an error, which is why the order of the two base-case lines matters.
• Duplicate values are fine: you compare by position, not by searching for values.

Related problems

• Subtree of Another Tree (LeetCode 572): runs this exact check at every node of a bigger tree.
• Invert Binary Tree (LeetCode 226): another two-line recursion on left and right.
• Serialize and Deserialize Binary Tree (LeetCode 297): the “serialise with null markers” idea, done properly.