Same Tree

Check whether two binary trees have the same shape and values.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Same Tree: Two trees match only if the same-position node pair passes the null, value, left-pair, and right-pair checks.

Input and goalCheck whether two binary trees have the same shape and values.

Pair the two rootsCompare A = [1,2,3] with B = [1,2,null]. Both roots exist and 1 == 1, so Python continues across the and-chain to the left pair.

• A:1 = B:1compare pair
  • A:2 = B:2
  • A:3 / B:null

callStack[(A:1,B:1)]checkboth real; 1 == 1

Recognize it

Use paired DFS when equality, symmetry, or structural correspondence requires comparing both value and shape at the same tree positions rather than comparing traversed value sequences.

Keep true

same_tree(first, second) returns true exactly when the two subtrees rooted at that pair have identical shape and equal values at every corresponding node.

Reuse it

When comparing recursive structures, recurse on aligned pairs and make missing-object cases explicit before reading values; this transfers to mirror symmetry, subtree equality, and AST comparison.

Pattern: DFS on two trees at the same time.

Simple idea: Two missing nodes match. One missing node does not match. Two real nodes match only when their values and both child pairs match.

def same_tree(first: TreeNode | None, second: TreeNode | None) -> bool:
   if first is None or second is None:
      return first is second
   return (
      first.val == second.val
      and same_tree(first.left, second.left)
      and same_tree(first.right, second.right)
   )

Cost: $O(n)$ time and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.