10. Same Tree
easyAsked at OlaDetermine whether two binary trees are structurally identical with equal values.
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 value.
Constraints
Number of nodes in each tree is in [0, 100]-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
Serialize both with sentinels for nulls and compare strings.
- Time
- O(n)
- Space
- O(n)
const ser = n => n ? `${n.val},${ser(n.left)},${ser(n.right)}` : '#';
return ser(p) === ser(q);Tradeoff:
2. DFS in parallel
Walk both trees together; bail on the first mismatch or null gap. O(min(n)) and O(h) stack.
- 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:
Ola-specific tips
Ola asks this to test parallel recursion fluency; mention the practical use of comparing two snapshots of a city-zone tree without rebuilding it.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.