10. Same Tree
easyAsked at InstacartDecide if two binary trees are structurally identical — Instacart probes recursion fluency before comparing inventory snapshots across stores.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given the roots of two binary trees p and q, return true if they are the same tree. Two binary trees are the same if they are structurally identical and the nodes have the same values.
Constraints
Both trees have 0 to 100 nodes-10^4 <= Node.val <= 10^4
Examples
Example 1
Input
p = [1,2,3], q = [1,2,3]Output
trueExample 2
Input
p = [1,2], q = [1,null,2]Output
falseApproaches
1. Serialize and compare
Stringify both trees in pre-order with null markers and compare.
- Time
- O(n)
- Space
- O(n)
function ser(n) {
if (!n) return '#';
return n.val + ',' + ser(n.left) + ',' + ser(n.right);
}
return ser(p) === ser(q);Tradeoff:
2. Parallel recursion
Recurse on both trees in lockstep; bail out on first mismatch.
- Time
- O(n)
- Space
- O(h)
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}Tradeoff:
Instacart-specific tips
Instacart wants the early-exit form — they'll ask how you'd extend it to confirm two inventory snapshots match across delivery regions.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.