Loading…

easyTreesLC #100Frequently asked

Same Tree

Q: How do you solve Same Tree using the Parallel Recursive DFS (Optimal) approach?

When to use it: Start and stay here — it's the cleanest solution and the one interviewers expect. Nail the null-check ordering. Equality of two trees is itself recursive: two trees are equal iff their roots match and their corresponding subtrees are equal. So write a function that takes one node from each tree and advances through both in lockstep. **Get the null cases right — and in order.** Three situations arise at each step. First, if *both* nodes are null, this position is consistently empty in both trees, so it matches — return true. Second, if *exactly one* is null (checked with `p == null || q == null` after the both-null case), the structures already diverge — return false. Only after those two guards is it safe to dereference `.val`, because both nodes are now guaranteed non-null. Flipping this order — comparing values first — risks a null-pointer exception, and dropping the one-null case makes structurally different trees compare equal. **The recursive case.** With both nodes non-null, they're equal here iff their values match *and* their left subtrees are equal *and* their right subtrees are equal. The `&&` / `and` short-circuits: the first failing condition stops the comparison, so a mismatch high in the tree never explores the rest. **Parallel, never crossed.** Compare left-with-left and right-with-right. This is what distinguishes Same Tree from Symmetric Tree — the latter crosses the recursion (left-with-right) to check mirror symmetry. Saying that contrast out loud shows you understand the structure rather than memorizing one snippet. **Why O(n) is optimal.** In the worst case (identical trees) you must inspect every node to be sure, so no algorithm can do better than linear. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Same Tree using the Iterative — Stack/Queue of Node Pairs approach?

When to use it: Offer if asked to avoid recursion or if very deep trees could overflow the call stack. The iterative version makes the pairing explicit. Instead of letting recursion match `p`'s node with `q`'s node, we store those pairs in a stack (or queue) and process them manually. **The loop.** Seed the container with the root pair `(p, q)`. Repeatedly pop a pair and apply the identical three-way logic: both null → consistent, skip; exactly one null → return false; both non-null with differing values → return false. When a pair passes, push its two child pairs `(a.left, b.left)` and `(a.right, b.right)` so they get checked too. If the container drains with no failure, every corresponding position matched → return true. **Why use it.** Functionally identical to the recursion; the only reason to prefer it is to dodge a deep call stack or because the interviewer explicitly asks for an iterative solution. Note the space is O(n) rather than the recursion's O(h), since the container can hold an entire level of pairs. Time complexity: O(n). Space complexity: O(n).

LCPractice

Trees & BST · 6 of 41 · 6 min

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

In plain English

Decide whether two trees are exact copies — same shape and same value at every corresponding position. We advance through both trees together; the moment the structure diverges (one node present where the other is null) or a value differs, they are not the same.

Examples

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true
Note: Identical structure and identical values at every node.

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false
Note: Same values but different structure — p has 2 as a left child, q has 2 as a right child.

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: false
Note: Same structure but the values differ at the children — left/right values are swapped.

Constraints

The number of nodes in both trees is in the range [0, 100]
-10⁴ ≤ Node.val ≤ 10⁴
Two empty trees are considered the same

Clarifying questions4First question: Are two empty trees the same?Explore questions

Q1.Are two empty trees the same?
Yes — both null is the base case that returns true.
Q2.Does structure matter, or only the multiset of values?
Structure matters. [1,2] (2 as left child) and [1,null,2] (2 as right child) hold the same values but are NOT the same tree.
Q3.Can values be negative?
Yes — values range down to -10⁴, so don't assume positivity. We only ever test equality, so sign is irrelevant to the logic.
Q4.Recursive or iterative?
Recursive parallel DFS is cleanest. An iterative version pushes pairs of nodes onto a stack/queue and checks them together — offer it if asked.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Two trees are the same if they have identical structure and identical values at every position. Walk both trees in lockstep: at each step both nodes must be null together, or both non-null with equal values and recursively-equal left and right subtrees. The null-handling order matters — check both-null and one-null BEFORE comparing values. O(n) time, O(h) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a clean two-pointer recursion over two trees and, critically, order the null checks correctly before dereferencing values.

Where candidates slip

Comparing p.val before checking that p and q are both non-null (null dereference), or forgetting the 'exactly one null → not equal' case so structurally different trees compare equal.

How to stand out

State the three-case null logic crisply, note that this is the building block for Subtree of Another Tree, and contrast it with Symmetric Tree where the recursion is crossed.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Parallel Recursive DFS (Optimal)Optimal	`O(n)`	`O(h)`	Start and stay here — it's the cleanest solution and the one interviewers expect. Nail the null-check ordering.	Read
2	Iterative — Stack/Queue of Node Pairs	`O(n)`	`O(n)`	Offer if asked to avoid recursion or if very deep trees could overflow the call stack.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAre the two trees identical?Recursion or explicit container?RecursionExplicitExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Parallel Recursive DFS (Optimal)

TimeO(n)SpaceO(h)

Start and stay here — it's the cleanest solution and the one interviewers expect. Nail the null-check ordering.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You're comparing two trees at once. What if your recursive function took TWO nodes, one from each tree, and advanced through both together?

2Hint 2Explore hint

Before touching values, reason about nulls: if both are null they match here; if exactly one is null the structures already differ.

3Hint 3Explore hint

When both are non-null, the node is equal iff values match AND the left pair matches AND the right pair matches — recurse left-with-left and right-with-right.

A · Core idea

Equality of two trees is itself recursive: two trees are equal iff their roots match and their corresponding subtrees are equal. So write a function that takes one node from each tree and advances through both in lockstep.

Get the null cases right — and in order. Three situations arise at each step. First, if both nodes are null, this position is consistently empty in both trees, so it matches — return true. Second, if exactly one is null (checked with p == null || q == null after the both-null case), the structures already diverge — return false. Only after those two guards is it safe to dereference .val, because both nodes are now guaranteed non-null. Flipping this order — comparing values first — risks a null-pointer exception, and dropping the one-null case makes structurally different trees compare equal.

The recursive case. With both nodes non-null, they're equal here iff their values match and their left subtrees are equal and their right subtrees are equal. The && / and short-circuits: the first failing condition stops the comparison, so a mismatch high in the tree never explores the rest.

Parallel, never crossed. Compare left-with-left and right-with-right. This is what distinguishes Same Tree from Symmetric Tree — the latter crosses the recursion (left-with-right) to check mirror symmetry. Saying that contrast out loud shows you understand the structure rather than memorizing one snippet.

Why O(n) is optimal. In the worst case (identical trees) you must inspect every node to be sure, so no algorithm can do better than linear.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Lockstep comparison of [1,2] vs [1,null,2]

How to read it:Roots match (1==1); then p.left=2 meets q.left=null → exactly one null → false.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

solution.javaJava

Parallel Recursive DFS (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isSameTree(TreeNode p, TreeNode q) {
10
    if (p == null && q == null) return true;    // both empty → match
11
    if (p == null || q == null) return false;   // exactly one empty → differ
12
    return p.val == q.val                        // values must match
13
        && isSameTree(p.left, q.left)            // left subtrees match
14
        && isSameTree(p.right, q.right);         // right subtrees match
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The whole problem hinges on a tidy three-way null decision made BEFORE any value comparison: both-null is true, one-null is false, both-non-null falls through to the value-and-subtree check. Recite that ladder and the code writes itself — and it's the exact helper you'll reuse inside Subtree of Another Tree.

ComplexityO(n) time, O(h) space — Each pair of corresponding nodes is compared once, so the work is O(min(n, m)) ≈ O(n) where n is the node count. Recursion depth is the tree height h → O(h) space. A mismatch short-circuits early, only ever making it faster.

E · Edge cases and pitfalls6p = [], q = [] — Both null at the top → returns true immediately.Explore edge cases

Edge cases handled

p = [], q = []Both null at the top → returns true immediately.
p = [1], q = []Exactly one null → returns false.
p = [1,2,3], q = [1,2,3]Every pair matches in value and structure → returns true after visiting all nodes.

Pitfalls

Comparing p.val == q.val before the null guards — null-pointer exception when one side is null.
Omitting the 'exactly one null' case — structurally different trees wrongly compare equal.
Crossing the recursion (p.left with q.right) — that solves Symmetric Tree, not Same Tree.

03.2

Approach 2 of 2

Iterative — Stack/Queue of Node Pairs

TimeO(n)SpaceO(n)

Offer if asked to avoid recursion or if very deep trees could overflow the call stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion implicitly pairs nodes. What if you stored those pairs explicitly in a stack or queue and checked them one at a time?

2Hint 2Explore hint

Push the pair (p, q). Pop a pair, apply the same null/value logic; if it passes, push the (left,left) and (right,right) child pairs.

3Hint 3Explore hint

If any popped pair fails the null or value check, return false. If the container empties without a failure, the trees are identical.

A · Core idea

The iterative version makes the pairing explicit. Instead of letting recursion match p's node with q's node, we store those pairs in a stack (or queue) and process them manually.

The loop. Seed the container with the root pair (p, q). Repeatedly pop a pair and apply the identical three-way logic: both null → consistent, skip; exactly one null → return false; both non-null with differing values → return false. When a pair passes, push its two child pairs (a.left, b.left) and (a.right, b.right) so they get checked too. If the container drains with no failure, every corresponding position matched → return true.

Why use it. Functionally identical to the recursion; the only reason to prefer it is to dodge a deep call stack or because the interviewer explicitly asks for an iterative solution. Note the space is O(n) rather than the recursion's O(h), since the container can hold an entire level of pairs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

push (1,1)

pop → both non-null, 1==1 → push (2,2),(3,3)

Statestack=[(2,2),(3,3)]

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isSameTree(TreeNode p, TreeNode q) { Deque<TreeNode[]> stack = new ArrayDeque<>(); stack.push(new TreeNode[]{p, q}); while (!stack.isEmpty()) { TreeNode[] pair = stack.pop();Explore the full code

solution.javaJava

Iterative — Stack/Queue of Node Pairs — reference

4 teaching notes

1
public boolean isSameTree(TreeNode p, TreeNode q) {
2
    Deque<TreeNode[]> stack = new ArrayDeque<>();
3
    // Seed with the root pair; each stack entry is a pair of corresponding nodes.
4
    stack.push(new TreeNode[]{p, q});
5
    while (!stack.isEmpty()) {
6
        TreeNode[] pair = stack.pop();
7
        TreeNode a = pair[0], b = pair[1];
8
        if (a == null && b == null) continue;       // consistent empty
9
        if (a == null || b == null) return false;    // structural mismatch
10
        if (a.val != b.val) return false;            // value mismatch
11
        // Queue up the corresponding child pair — left with left.
12
        stack.push(new TreeNode[]{a.left, b.left});
13
        stack.push(new TreeNode[]{a.right, b.right});
14
    }
15
    return true;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Any parallel recursion can be made iterative by storing the pairs that the recursion would have created. The trick is remembering to push child pairs only after the current pair passes its checks — otherwise you'd dereference a null.

ComplexityO(n) time, O(n) space — Each corresponding node pair is pushed and popped once → O(n) time. The container can hold up to O(n) pairs in the worst case (e.g. a wide level), so O(n) space — slightly worse than the recursion's O(h).

E · Edge cases and pitfalls6p = [], q = [] — First popped pair is (null,null) → continue → stack empties → true.Explore edge cases

Edge cases handled

p = [], q = []First popped pair is (null,null) → continue → stack empties → true.
p = [1,2], q = [1,null,2]The (2, null) child pair triggers the one-null guard → false.
Deep skewed identical treesStack holds at most O(h) pairs here, but O(n) in the worst wide case.

Pitfalls

Pushing child pairs before the null/value checks pass — risks dereferencing a null later.
Forgetting `continue` on the both-null case and instead falling through to push nulls indefinitely.
Using a single-node stack instead of pairs — you must track both trees together.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Value comparison before null guards

If one node is null and you read .val first, you get a NullPointerException / AttributeError. The null cases must be resolved before any dereference.

Explore the code comparison

Don't write this

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p.val != q.val) return false;   // crashes when p or q is null
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Write this instead

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

Missing the one-null case

Without the 'exactly one null' guard, a tree and a structurally different tree (one has a child where the other doesn't) can fall through and wrongly compare equal.

Explore the code comparison

Don't write this

def isSameTree(self, p, q):
    if not p and not q:
        return True
    # missing: one null -> False
    return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Write this instead

def isSameTree(self, p, q):
    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))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Parallel (lockstep) DFS comparing two trees node-for-node

Code pattern to memorize

same(p, q):
    if p is null and q is null: return True
    if p is null or q is null: return False   # exactly one null → differ
    return p.val == q.val
       and same(p.left, q.left)
       and same(p.right, q.right)

Rules to remember

1Handle nulls first: both-null → equal; exactly-one-null → not equal. Only then compare .val.
2Recurse in parallel — left-with-left and right-with-right, never crossed (crossing is the Symmetric-Tree problem).
3Structure AND values must both match — same shape with different numbers is not the same tree.
4Short-circuit with && / and: the first mismatch ends the comparison early.
5Both empty trees are the same tree (return true).

Use this pattern when

You must check two trees for exact equality of shape and values
Any lockstep traversal of two structures advanced together
A helper inside larger problems (Subtree of Another Tree, Symmetric Tree)

Choose another pattern when

You compare a tree against its own mirror → Symmetric Tree (cross the recursion)
You search one tree for a matching subtree → Subtree of Another Tree (call sameTree at each node)
Only values matter, not structure → serialize and compare strings instead

Interview takeaway

Same Tree is the canonical parallel-DFS: advance two pointers through two trees together, and at each step verify the null pattern matches, the values match, and both subtrees recursively match. It's the equality primitive that Subtree of Another Tree and Symmetric Tree are built on top of.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternParallel DFS: advance two structures together and compare them position-by-position. The careful three-way null handling (both-null, one-null, both-non-null) is the reusable core. This equality primitive is embedded inside Subtree of Another Tree and twisted (crossed) into Symmetric Tree.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Symmetric Tree
Compare a tree against itself but CROSS the recursion: left-with-right and right-with-left.
Subtree of Another Tree
Run isSameTree at every node of the big tree to test if the small tree matches there.
Invert Binary Tree
The transformation cousin — swap children instead of comparing two trees.
Flip Equivalent Binary Trees
Coming soon
Like Same Tree but children may be swapped — try both matched and crossed recursions.

Same pattern

←

Balanced Binary Tree

Continue · Next problem

Subtree of Another Tree

easyTreesLC #100Frequently asked

Same Tree

LCPractice

Trees & BST · 6 of 41 · 6 min

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

In plain English

Examples

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true
Note: Identical structure and identical values at every node.

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false
Note: Same values but different structure — p has 2 as a left child, q has 2 as a right child.

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: false
Note: Same structure but the values differ at the children — left/right values are swapped.

Constraints

The number of nodes in both trees is in the range [0, 100]
-10⁴ ≤ Node.val ≤ 10⁴
Two empty trees are considered the same

Clarifying questions4First question: Are two empty trees the same?Explore questions

Q1.Are two empty trees the same?
Yes — both null is the base case that returns true.
Q2.Does structure matter, or only the multiset of values?
Structure matters. [1,2] (2 as left child) and [1,null,2] (2 as right child) hold the same values but are NOT the same tree.
Q3.Can values be negative?
Yes — values range down to -10⁴, so don't assume positivity. We only ever test equality, so sign is irrelevant to the logic.
Q4.Recursive or iterative?
Recursive parallel DFS is cleanest. An iterative version pushes pairs of nodes onto a stack/queue and checks them together — offer it if asked.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a clean two-pointer recursion over two trees and, critically, order the null checks correctly before dereferencing values.

Where candidates slip

Comparing p.val before checking that p and q are both non-null (null dereference), or forgetting the 'exactly one null → not equal' case so structurally different trees compare equal.

How to stand out

State the three-case null logic crisply, note that this is the building block for Subtree of Another Tree, and contrast it with Symmetric Tree where the recursion is crossed.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Parallel Recursive DFS (Optimal)Optimal	`O(n)`	`O(h)`	Start and stay here — it's the cleanest solution and the one interviewers expect. Nail the null-check ordering.	Read
2	Iterative — Stack/Queue of Node Pairs	`O(n)`	`O(n)`	Offer if asked to avoid recursion or if very deep trees could overflow the call stack.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Parallel Recursive DFS (Optimal)

TimeO(n)SpaceO(h)

Start and stay here — it's the cleanest solution and the one interviewers expect. Nail the null-check ordering.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You're comparing two trees at once. What if your recursive function took TWO nodes, one from each tree, and advanced through both together?

2Hint 2Explore hint

Before touching values, reason about nulls: if both are null they match here; if exactly one is null the structures already differ.

3Hint 3Explore hint

When both are non-null, the node is equal iff values match AND the left pair matches AND the right pair matches — recurse left-with-left and right-with-right.

A · Core idea

Why O(n) is optimal. In the worst case (identical trees) you must inspect every node to be sure, so no algorithm can do better than linear.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Lockstep comparison of [1,2] vs [1,null,2]

How to read it:Roots match (1==1); then p.left=2 meets q.left=null → exactly one null → false.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

solution.javaJava

Parallel Recursive DFS (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isSameTree(TreeNode p, TreeNode q) {
10
    if (p == null && q == null) return true;    // both empty → match
11
    if (p == null || q == null) return false;   // exactly one empty → differ
12
    return p.val == q.val                        // values must match
13
        && isSameTree(p.left, q.left)            // left subtrees match
14
        && isSameTree(p.right, q.right);         // right subtrees match
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6p = [], q = [] — Both null at the top → returns true immediately.Explore edge cases

Edge cases handled

p = [], q = []Both null at the top → returns true immediately.
p = [1], q = []Exactly one null → returns false.
p = [1,2,3], q = [1,2,3]Every pair matches in value and structure → returns true after visiting all nodes.

Pitfalls

Comparing p.val == q.val before the null guards — null-pointer exception when one side is null.
Omitting the 'exactly one null' case — structurally different trees wrongly compare equal.
Crossing the recursion (p.left with q.right) — that solves Symmetric Tree, not Same Tree.

03.2

Approach 2 of 2

Iterative — Stack/Queue of Node Pairs

TimeO(n)SpaceO(n)

Offer if asked to avoid recursion or if very deep trees could overflow the call stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion implicitly pairs nodes. What if you stored those pairs explicitly in a stack or queue and checked them one at a time?

2Hint 2Explore hint

Push the pair (p, q). Pop a pair, apply the same null/value logic; if it passes, push the (left,left) and (right,right) child pairs.

3Hint 3Explore hint

If any popped pair fails the null or value check, return false. If the container empties without a failure, the trees are identical.

A · Core idea

The iterative version makes the pairing explicit. Instead of letting recursion match p's node with q's node, we store those pairs in a stack (or queue) and process them manually.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

push (1,1)

pop → both non-null, 1==1 → push (2,2),(3,3)

Statestack=[(2,2),(3,3)]

Final resulttrue

C · Code with teaching comments

solution.javaJava

Iterative — Stack/Queue of Node Pairs — reference

4 teaching notes

1
public boolean isSameTree(TreeNode p, TreeNode q) {
2
    Deque<TreeNode[]> stack = new ArrayDeque<>();
3
    // Seed with the root pair; each stack entry is a pair of corresponding nodes.
4
    stack.push(new TreeNode[]{p, q});
5
    while (!stack.isEmpty()) {
6
        TreeNode[] pair = stack.pop();
7
        TreeNode a = pair[0], b = pair[1];
8
        if (a == null && b == null) continue;       // consistent empty
9
        if (a == null || b == null) return false;    // structural mismatch
10
        if (a.val != b.val) return false;            // value mismatch
11
        // Queue up the corresponding child pair — left with left.
12
        stack.push(new TreeNode[]{a.left, b.left});
13
        stack.push(new TreeNode[]{a.right, b.right});
14
    }
15
    return true;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6p = [], q = [] — First popped pair is (null,null) → continue → stack empties → true.Explore edge cases

Edge cases handled

p = [], q = []First popped pair is (null,null) → continue → stack empties → true.
p = [1,2], q = [1,null,2]The (2, null) child pair triggers the one-null guard → false.
Deep skewed identical treesStack holds at most O(h) pairs here, but O(n) in the worst wide case.

Pitfalls

Pushing child pairs before the null/value checks pass — risks dereferencing a null later.
Forgetting `continue` on the both-null case and instead falling through to push nulls indefinitely.
Using a single-node stack instead of pairs — you must track both trees together.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Value comparison before null guards

If one node is null and you read .val first, you get a NullPointerException / AttributeError. The null cases must be resolved before any dereference.

Explore the code comparison

Don't write this

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p.val != q.val) return false;   // crashes when p or q is null
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Write this instead

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

Missing the one-null case

Without the 'exactly one null' guard, a tree and a structurally different tree (one has a child where the other doesn't) can fall through and wrongly compare equal.

Explore the code comparison

Don't write this

def isSameTree(self, p, q):
    if not p and not q:
        return True
    # missing: one null -> False
    return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Write this instead

def isSameTree(self, p, q):
    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))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Parallel (lockstep) DFS comparing two trees node-for-node

Code pattern to memorize

same(p, q):
    if p is null and q is null: return True
    if p is null or q is null: return False   # exactly one null → differ
    return p.val == q.val
       and same(p.left, q.left)
       and same(p.right, q.right)

Rules to remember

1Handle nulls first: both-null → equal; exactly-one-null → not equal. Only then compare .val.
2Recurse in parallel — left-with-left and right-with-right, never crossed (crossing is the Symmetric-Tree problem).
3Structure AND values must both match — same shape with different numbers is not the same tree.
4Short-circuit with && / and: the first mismatch ends the comparison early.
5Both empty trees are the same tree (return true).

Use this pattern when

You must check two trees for exact equality of shape and values
Any lockstep traversal of two structures advanced together
A helper inside larger problems (Subtree of Another Tree, Symmetric Tree)

Choose another pattern when

You compare a tree against its own mirror → Symmetric Tree (cross the recursion)
You search one tree for a matching subtree → Subtree of Another Tree (call sameTree at each node)
Only values matter, not structure → serialize and compare strings instead

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Symmetric Tree
Compare a tree against itself but CROSS the recursion: left-with-right and right-with-left.
Subtree of Another Tree
Run isSameTree at every node of the big tree to test if the small tree matches there.
Invert Binary Tree
The transformation cousin — swap children instead of comparing two trees.
Flip Equivalent Binary Trees
Coming soon
Like Same Tree but children may be swapped — try both matched and crossed recursions.

Same pattern

←

Balanced Binary Tree

Continue · Next problem

Subtree of Another Tree