Same Tree
The Prompt
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.
Understanding the Problem
Two trees are the same when they have identical shape and identical values at every corresponding position. A single differing value or a child that exists in one tree but not the other makes them different.
The recursive reframe: p and q are the same iff their roots hold equal values, their left subtrees are the same, and their right subtrees are the same. Two nulls are trivially the same; one null and one node are trivially different.
The Interview Flow
Interviewer
How would you determine if two binary trees are identical?
Candidate
This seems like a perfect problem for recursion. I need to check two conditions: structural identity and value identity.
Interviewer
What would be your base cases?
Candidate
There are a few. If both nodes `p` and `q` are null, they are identical, so I return true. If one is null but the other isn't, they are not identical, so I return false. If their values are different, I return false.
Interviewer
And the recursive step?
Candidate
If the base cases pass (they are both non-null and have the same value), then I need to ensure their subtrees are also identical. I would recursively call the function on their left children (`isSameTree(p.left, q.left)`) and their right children (`isSameTree(p.right, q.right)`). The trees are identical only if both of these recursive calls return true.
Interviewer
That covers all conditions. The logic is clean and correct. Please code it.
Why does comparing node-by-node in lockstep suffice?
The invariant is that sameTree(p, q) is true exactly when the subtrees rooted at p and q match position for position. The base cases pin it down (null/null → true, null/node → false, unequal values → false), and the recursive case ANDs the two child comparisons — so any mismatch anywhere propagates up as false, and the recursion short-circuits at the first difference.
Time is O(min(n, m)): the walk stops as soon as a mismatch appears and never explores past the smaller tree. Space is O(h) recursion depth.
Recursive Pre-order Traversal
- Define a function `isSameTree` that takes two nodes, `p` and `q`.
- Handle the base cases first:
- If both `p` and `q` are `null`, return `true`.
- If either `p` or `q` is `null` (but not both), or if `p.val` is not equal to `q.val`, return `false`.
- If the current nodes are valid, perform the recursive step: return the result of `isSameTree(p.left, q.left)` AND `isSameTree(p.right, q.right)`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}Explanation
Compare p = [1, 2, 3] and q = [1, 2, 3] — the two traversals move in lockstep.
1Compare the roots: 1 vs 1 — equal. Neither is null, so recurse into the left pair and then the right pair.
2Left pair: 2 vs 2 — equal, and both are leaves (their null children match trivially), so the left comparison returns true.
3Right pair: 3 vs 3 — equal leaves. Every corresponding pair matched, so the trees are the same: return true.
Complexity Analysis
TIME
O(n)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.