Same Tree

1. Problem & Core Objective

Given the roots of two binary trees, return true if they are structurally identical and every corresponding node holds the same value.

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

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

Constraints: 0 <= nodes <= 100 · -10^4 <= Node.val <= 10^4

What's actually being tested: recursing over two trees in lockstep. It's a small variation on the single-tree recursion, and it's the routine that question 6 (Subtree of Another Tree) calls repeatedly.

2. First-Principles Thought Process

The contract, with two arguments

same(p, q) is true when the subtree at p is identical to the subtree at q.

Two trees are identical when three things hold at every node:

1. Both are null, or both are non-null — structure matches
2. Their values are equal — contents match
3. Their left subtrees are identical, and their right subtrees are identical — trust the contract

The null cases are the whole problem

There are three distinct situations, and collapsing them wrongly is the usual bug:

So:

if (p == null && q == null) return true;      // both empty
if (p == null || q == null) return false;     // exactly one empty

The second line works only because the first already ran — at that point, "one is null" implies "exactly one is null". Order matters, and it's what lets two lines cover three cases.

Why structure must be checked before values

p.val == q.val throws a NullPointerException if either is null. The null checks aren't defensive padding — they're what makes the value comparison legal.

3. Solution Paths

Approach 1 — Serialize both and compare strings (brute force)

public boolean isSameTree(TreeNode p, TreeNode q) {
    return serialize(p).equals(serialize(q));
}

private String serialize(TreeNode n) {
    if (n == null) return "#";                        // the null marker is essential
    return n.val + "," + serialize(n.left) + "," + serialize(n.right);
}

• Time O(n) to build, plus O(n) to compare · Space O(n) for the strings

Counter-questions on this approach

⭐ "Why is the # marker essential? What breaks without it?"

Without null markers, preorder is ambiguous — different trees produce identical strings. A node with only a left child and a node with only a right child both serialize to the same sequence of values. The marker records where the structure ends, which is exactly the information that distinguishes them.

This is the core idea of question 15, and it's worth getting right even in a solution I'm about to reject.

⭐ "Why reject it?"

It builds two O(n) strings to answer a boolean, and the concatenation makes it worse than it looks — n.val + "," + left + "," + right allocates a new string at every node, so it's closer to O(n²) in practice unless you pass a StringBuilder down.

The direct recursion answers the same question with no allocation and short-circuits on the first mismatch, which the string version can't.

"Would comparing hashes be faster?"

It would avoid holding the strings, but hashing still walks both trees fully and introduces collision risk — you'd need to verify on a match anyway. For a single comparison it's strictly worse. Hashing subtrees does pay off when you compare many pairs, which is the optimisation in question 6.

Approach 2 — Parallel recursion (optimal)

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;      // both empty
    if (p == null || q == null) return false;     // exactly one empty
    if (p.val != q.val)         return false;     // values differ

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

• Time O(min(n, m)) — stops at the first difference · Space O(h) stack

Counter-questions on this approach

⭐ "Walk me through those first two lines. Why is that enough for three cases?"

The first handles both-null. Once it has not returned, at least one of them is non-null — so the second line's p == null || q == null can only be true when exactly one is null, which is a structural mismatch.

Reversing the order breaks it: if (p == null || q == null) return false; first would reject two empty subtrees, and every leaf comparison would fail.

⭐ "Why is the time O(min(n, m)) rather than O(n)?"

Because && short-circuits and every mismatch returns immediately. If the trees differ at the root, it's O(1). The work is bounded by the size of the smaller tree, since the recursion stops as soon as one side runs out of nodes where the other has some.

Worst case — identical trees — it is O(n), because it must check everything to conclude they match.

"Does && versus & matter on the last line?"

Yes. && short-circuits, so a mismatch in the left subtree skips the right entirely. & would evaluate both, doing unnecessary work — correct, but slower, and on a large tree noticeably so.

"Could you compare values before the null checks?"

No — p.val throws when p is null. The null checks must come first, and that's not stylistic.

"Does traversal order matter — could you check right before left?"

No effect on correctness. It only changes which mismatch you find first, and therefore how quickly you exit on a particular input. Preorder is conventional and makes the short-circuit intuitive.

Comparison

4. Why the Optimal Wins

The recursion answers the question directly, allocates nothing, and stops at the first disagreement. Serialization computes a complete description of both trees in order to compare them — far more information than a boolean needs.

The early exit is the real difference. Two trees that differ at the root are O(1) for the recursion and O(n) for serialization.

The framing worth keeping:

To compare two trees, recurse over both in lockstep. Handle both-null, exactly-one-null, and values — in that order — then trust the contract for the children.

5. Java Prerequisites

The two-tree null ladder — order is load-bearing:

if (p == null && q == null) return true;
if (p == null || q == null) return false;

Short-circuit && stops at the first false, which gives both the early exit and the null safety.

Reference vs value equality

p == q            // same object
p.val == q.val    // same value — what this problem wants

TreeNode doesn't override equals, so p.equals(q) is identity — not what you want here.

String concatenation in recursion. a + "," + b allocates a new string each time. Use a StringBuilder passed down if you serialize for real — see question 15.

6. Interview Communication Guide

Clarifying questions: Must structure match as well as values (yes — that's the point)? Can either root be null (yes, both)? Are duplicate values possible (yes; irrelevant, since position is compared too)?

The pitch

"Two trees are identical when, at every node, the structure matches and the values match. So I recurse over both in lockstep.

The null handling is the part worth being careful about, because there are three cases. Both null is true — two empty subtrees are identical. Exactly one null is false — the structure differs. Otherwise compare values, then recurse on both children.

I write that as two lines: both null → true, then either null → false. The second is only correct because the first already returned — at that point 'either is null' implies 'exactly one is null'. Reversing them would reject every leaf.

The null checks also have to precede the value comparison, or p.val throws.

Time is O(min(n, m)) because && short-circuits and any mismatch returns immediately — trees differing at the root exit in O(1). Worst case, identical trees, it's O(n). Space is O(h) for the stack."

Edge cases to volunteer:

Name [1,2] vs [1,null,2]. Same multiset of values, different shape — it's the case that proves you're comparing structure, and it's what the # marker exists for in the serialization approach.

7. Follow-Up Questions — Modified Constraints

⭐ "Check whether one tree is a SUBTREE of another."

Question 6. Walk the big tree and call this function at every node: isSame(node, sub). That's O(n × m) in the worst case, since each of n roots may compare m nodes. The linear-time alternative is to serialize both with null markers and run a substring search — which is exactly why the serialization approach above was worth understanding rather than just dismissing.

⭐ "Check whether two trees are MIRRORS of each other."

LeetCode 101. Same recursion with the children crossed: mirror(p.left, q.right) && mirror(p.right, q.left). One character of difference in each call, and it's a good check of whether the lockstep idea was understood or memorized.

"Compare two n-ary trees."

Check that the children lists are the same length, then zip and recurse pairwise. The null ladder generalizes to a size comparison.

"What if nodes carried extra fields that should be ignored?"

Replace p.val != q.val with a comparison over only the relevant fields, or take a BiPredicate<TreeNode, TreeNode> parameter. The traversal is unchanged — only the per-node test varies, which is a clean separation worth pointing out.

"Compare trees where child order doesn't matter — [1,2,3] equals [1,3,2]."

Much harder. You'd need a canonical form: recursively compute a sorted signature of each node's subtrees, then compare those. Sorting at each node makes it O(n log n) overall. This is the tree-isomorphism problem, and worth flagging as substantially different from lockstep comparison.

"What if the trees were enormous and mostly identical?"

Merkle hashing — store a hash of each subtree in its node, and compare hashes to skip identical regions in O(1). That's how git compares directory trees and how distributed systems detect replica divergence. The trade is that hashes must be maintained on every mutation.