4.14.5 — Same Tree

LeetCode 100 · Easy · ★ Blind 75

The problem

Return true if two binary trees have the same structure and the same values.

  1        1
 / \      / \      →  true
2   3    2   3

  1        1
 /          \      →  false   (same values, different shape)
2            2

The pattern

Two trees are the same when their roots match and both pairs of subtrees are the same. Walk them together, one step at a time.

Three cases at each pair of nodes:

• Both empty — the same. This is the base case.
• One empty, the other not — different shape, so different.
• Both present — the values must match, and both subtree pairs must match.

The solution

Python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return (p.val == q.val
                and self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))

TypeScript

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

The order of the two base cases matters. not p and not q must come first. If you checked not p or not q first, two empty trees would take that branch and return false.

and short-circuits, so a mismatch stops the walk immediately rather than exploring the rest.

Complexity

O(n) time, where n is the size of the smaller tree — the walk stops at the first difference. O(h) space.

The traversal trap

A tempting shortcut is to serialise both trees and compare the strings. Be careful: a single traversal order does not determine a tree.

  1          1
 /            \
2              2

Both give [1, 2] in pre-order if you skip the empty children. They are different trees.

The fix is to include the nulls in the serialisation — "1,2,#,#,#" versus "1,#,2,#,#" — which makes it unambiguous. That is exactly why 4.14.15 Serialize and Deserialize writes markers for empty children.

Two traversals together — in-order plus pre-order — also determine a tree, which is the basis of 4.14.13.

Where this goes next

• Symmetric Tree — is a tree its own mirror? The same comparison, but walking left.left against right.right and left.right against right.left.
• Subtree of Another Tree — use this function as a helper at every node of the bigger tree. That is the very next page, 4.14.6.
• Merge Two Binary Trees — the same simultaneous walk, building a new tree instead of comparing.

The rule: to compare or combine two trees, recurse on both at once and handle the three null cases first.

Next: 4.14.6 Subtree of Another Tree — this function used as a subroutine, with an unexpectedly fast alternative.