10. Same Tree
easyAsked at GlassdoorDetermine whether two binary trees are identical in shape and values — Glassdoor uses this to grade recursive base-case discipline.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given the roots of two binary trees p and q, write a function to check if they are the same tree. Two trees are the same if they are structurally identical and the nodes have the same values.
Constraints
Number of nodes in each tree is in [0, 100]-10^4 <= Node.val <= 10^4
Examples
Example 1
p = [1,2,3], q = [1,2,3]trueExample 2
p = [1,2], q = [1,null,2]falseApproaches
1. Serialize and compare
Stringify both trees with delimiters and compare.
- Time
- O(n)
- Space
- O(n)
function serialize(n) {
if (!n) return '#';
return n.val + ',' + serialize(n.left) + ',' + serialize(n.right);
}
return serialize(p) === serialize(q);Tradeoff:
2. Recursive DFS comparison
Both roots null = true; one null = false; otherwise compare values and recurse.
- 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:
Glassdoor-specific tips
Glassdoor grades for explicit null base cases — they value engineers who walk through them aloud since their review-deduplication trees hit deep-null paths constantly.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.