10. Same Tree
easyAsked at LyftCheck whether two binary trees are structurally identical with the same 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 trees are the same if they are structurally identical and the nodes have the same value.
Constraints
Number of nodes in both trees in range [0, 100]-10^4 <= node value <= 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 trees and compare strings.
- Time
- O(n)
- Space
- O(n)
function ser(n){return !n? '#': n.val+','+ser(n.left)+','+ser(n.right);}
return ser(p)===ser(q);Tradeoff:
2. Recursive structural compare
Compare current node values, then recurse left and right in lockstep.
- 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:
Lyft-specific tips
Lyft asks about tree equality during the diff stage of region-shape comparisons; explicit nullability handling earns bonus signal in the matching service context.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.