Introduction to Comparison of Two Trees Pattern

Comparing two trees works by walking both trees in lockstep — advancing one pointer per tree per step — and asserting at every visited pair of nodes that both are null, or both are non-null with equal values and recursively equal subtrees; a single mismatched shape or value at any depth is a global no-match, so the check can short-circuit the instant it finds one.

Recognize the pattern

• Problem gives you two (or more) tree roots and asks "same?", "mirror?", "is one a subtree of the other?", "merge two trees?"
• You need to check structural equality — not just node count or a set of values, but shape AND position AND value together.
• A single tree traversal (like normal DFS) is not enough — you need a function whose recursive calls take a pair of nodes, not one.

Brute force → optimal

Brute force: serialize each tree (e.g., preorder string with null markers) then compare the two strings. Costs O(n) time to build each serialization plus O(n) string comparison, but O(n) extra space for two full serializations, and it is easy to get null-marker escaping wrong (e.g., values that look like markers).

Optimal: paired recursion (DFS) directly on the two trees, no serialization buffer — same O(n) time, but O(h) auxiliary space (recursion stack, h = height) instead of O(n). This is the standard interview-accepted solution.

Complexity, derived

Let n = number of nodes in the smaller tree (traversal stops as soon as a mismatch or a null is hit on either side). The recursion visits each pair of corresponding nodes at most once: T(n) = 2·T(n/2) + O(1) in the balanced case, which unrolls to O(n) total node-pair visits since every node is compared exactly once before recursion ends for that branch. Early exit on mismatch only improves the constant, not the worst case (identical trees force a full visit).

Space: the call stack depth equals the current recursion depth, which is bounded by the height h of the trees — O(h), i.e. O(log n) balanced, O(n) for a degenerate (skewed) tree.

Worked example

root1 = [3,7,9], root2 = [3,7,9] (both: root 3, left 7, right 9, all leaves).

Now root2's right leaf value is changed to 8: at step 3, same(9,8) fails the value check immediately — recursion returns false without visiting anything below (there is nothing below), and the result propagates up as false.

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

Pitfalls

• Checking only p.val == q.val without first handling the null/null and null/non-null cases → NullPointerException.
• Using &/| instead of &&/|| — loses short-circuiting, forcing full traversal even after a mismatch (correctness is unaffected but wastes work).
• Confusing "same tree" with "subtree" or "symmetric tree" — subtree search requires trying isSameTree at every node of the larger tree; symmetric tree compares a tree against its own mirror (left vs right, not left vs left).
• For BFS-based comparison, forgetting to enqueue null markers means you lose structural information about missing children.

When to use / when not

Use paired DFS when you need exact structural+value equality, mirror checks, or merging two trees — it is O(n) time, O(h) space, and simplest to reason about recursively.

vs. Serialization compare (alternative): serialization is useful when you must compare a tree against many other trees repeatedly (e.g., hashing each tree once, then O(1) amortized comparisons) — trades O(n) extra space and a preprocessing pass for cheaper repeated comparisons. For a single one-off comparison, paired DFS is strictly better (no extra space, no encoding edge cases).

vs. Iterative BFS with two queues: equivalent time/space complexity (O(n) time, O(w) queue space where w is max width) but avoids recursion depth limits on very deep/skewed trees — prefer BFS if trees can be pathologically unbalanced and stack overflow is a risk.

How the skeleton flexes — the comparison rule is the only thing that changes. Symmetric (LeetCode 101) recurses isMirror(a.left, b.right) && isMirror(a.right, b.left) — same-value check, mirrored children. Subtree of another tree (LeetCode 572) wraps this: run isSameTree anchored at every node of the larger tree, giving O(m·n) in the naive form. Flip-equivalent / isomorphic (LeetCode 951) allows a node's children to be swapped, so at each pair you accept either same(a.left,b.left) && same(a.right,b.right) OR same(a.left,b.right) && same(a.right,b.left). Trying both orderings at every node is still O(n) because you short-circuit on the first arrangement that matches — the trap is writing it so both branches are explored unconditionally even after one succeeds, which risks exponential blow-up.

Takeaways

• Comparison pattern = recursion over pairs of nodes, not single nodes; base cases handle the two null combinations first.
• Time is O(n) (visit each pair once); space is O(h) for the call stack, not O(n).
• Mismatch short-circuits immediately — no need to keep comparing once one pair fails.
• Variants (subtree, symmetric, merge) all reuse this same paired-recursion skeleton with a different comparison rule.

Recall: Why does checking p == null && q == null before p.val == q.val matter, and what happens if you skip the null checks entirely?

Synthesized from standard binary tree equality/comparison techniques (LeetCode "Same Tree", "Symmetric Tree", "Subtree of Another Tree" patterns) and classic recursive tree-traversal analysis.