Same Tree — LeetCode 100 Parallel DFS Comparison

Problem Statement#

Given the roots of two binary trees p and q, determine if they are the same tree — identical in structure and node values.

Constraints:

• Number of nodes in either tree is in the range [0, 100].
• -10^4 <= Node.val <= 10^4.

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

Input:  p = [1,2], q = [1,null,2]
Output: false

Why This Problem Matters#

LeetCode 100 — Same Tree is the prototype "compare two trees" question. Amazon, Meta, Google, and Apple use it as a 5-minute warmup. It is also the building block for Subtree of Another Tree (LC 572), where you call isSameTree from inside a tree walk.

What makes it "interview material" rather than trivial is the two base cases: both null versus exactly one null. Many candidates collapse them into one check and silently return wrong answers. Recruiters watch for the careful order of those checks.

It also tests whether you can write a recursion with two simultaneous arguments, the same skill used by Symmetric Tree, Merge Two Binary Trees, and Flip Equivalent Binary Trees.

The Core Insight#

Two trees are equal iff:

1. Both roots are null, or
2. Both roots are non-null, their values match, and their corresponding subtrees are pairwise equal.

A pure recursive base case + AND of three conditions captures the entire algorithm in five lines.

Visual Dry Run#

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

Result: true.

For p = [1, 2] and q = [1, null, 2] step 2 compares (2, null) and immediately returns false.

Solution (Optimal)#

# Python — recursive parallel DFS
class Solution:
    def isSameTree(self, p, q):
        if not p and not q: return True   # both empty -> equal
        if not p or not q:  return False  # one empty -> unequal
        return (p.val == q.val
                and self.isSameTree(p.left,  q.left)
                and self.isSameTree(p.right, q.right))

// JavaScript — same recursion
var isSameTree = function(p, q) {
    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);
};

# Iterative BFS — pair queue
from collections import deque
class Solution:
    def isSameTree(self, p, q):
        q_pairs = deque([(p, q)])
        while q_pairs:
            a, b = q_pairs.popleft()
            if not a and not b: continue
            if not a or not b or a.val != b.val: return False
            q_pairs.append((a.left,  b.left))
            q_pairs.append((a.right, b.right))
        return True

Time: O(n) where n is the size of the smaller tree (we short-circuit on mismatch). Space: O(h) recursion stack or O(w) BFS queue.

Common Mistakes#

• Collapsing the two base cases into if not p or not q: return p == q — works only if both None evaluate equal, but breaks reasoning.
• Comparing values before checking nullity — p.val on a null pointer crashes.
• Recursing into only left and forgetting right.
• Using p == q as a Python value comparison without __eq__ defined; it actually tests identity, which is unrelated to tree equality.

Interview Tips#

• Always order the base cases: "both null first, exactly one null second, then recurse".
• Mention that the function short-circuits on the first mismatch — that is why O(n) is a worst-case bound.
• Bring up Subtree of Another Tree (LC 572) as the natural next step.
• For very deep skewed trees, the iterative version is safer.

Follow-up Questions#

• Subtree of Another Tree (LC 572)? Walk one tree, call isSameTree at each node.
• Flip Equivalent Binary Trees (LC 951)? Like Same Tree but allow swapping children at any node.
• Hash-based comparison? Tree hash with Merkle-style postorder for O(n) average comparison.
• Compare structures only, ignore values? Drop the value check; keep the null/null and null/non-null branches.
• Stream comparison without loading both trees? Walk both with synchronized iterators.

Key Takeaways#

• LeetCode 100 Same Tree runs in O(n) time and O(h) space.
• Two base cases: both null returns true, exactly one null returns false.
• Recursion is val == val and left == left and right == right.
• Asked at Amazon, Meta, Google, Apple, Bloomberg as a phone-screen opener.
• Foundation for Subtree of Another Tree (LC 572) and Flip Equivalent Binary Trees (LC 951).
• BFS pair-queue is the iterative variant — same O(n) time.
• Short-circuits on the first mismatch, so average-case performance is much better than worst case.