Same Tree

Problem

Configuration management systems compare deployment snapshots as trees to detect drift. When two independently-built trees must be diff-checked for exact equivalence, you need structural and value equality at every node. Given the roots of two binary trees, return true if they are structurally identical with the same node values at every position.

  1       1
 / \     / \
2   3   2   3
→ True
 
  1       1
 /         \
2           2
→ False

Solution

Approach - Simultaneous DFS over both trees with three base cases.

Walk both trees in lockstep, comparing the node at the same position in each. Correctness comes from handling the None cases exhaustively and in the right order. First check both-None - if p and q are both absent, this position matches, so return True. Only then check one-None - if exactly one is absent, the trees differ structurally (one has a node where the other has a gap), so return False. The ordering matters: testing one-None first would wrongly reject the both-None case. Once past the None checks, both nodes exist, so compare their values and recurse on both child pairs: p.val == q.val and same_tree(p.left, q.left) and same_tree(p.right, q.right).

The and chain short-circuits, which is both a correctness convenience and a speed win - if the values differ at a node, the recursive calls never fire, and a difference near the root returns False in O(1) instead of scanning the whole tree. Trace [1,2,None] against [1,None,2]. Roots match (1 == 1). Recursing left, p.left is node 2 but q.left is None - exactly one is None, so that branch returns False, and the and propagates False all the way up. The structure differs even though both trees contain a 1 and a 2; the None check catches the positional mismatch before values would ever mislead.

Edge cases - Two None roots return True (identical empty trees). One None root with a real node returns False. Trees that share values but differ in shape are correctly rejected by the one-None check.

Complexity - O(n) time over the smaller tree, O(h) space for the call stack - every overlapping position is compared once, recursion bounded by the height.