10. Same Tree
easyAsked at SlackDetermine if two binary trees are identical in structure and value.
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
Nodes count 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 trees to strings, compare.
- 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
Both null is equal; one null is unequal; otherwise check values and recurse on children.
- 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:
Slack-specific tips
Slack channel-config diff (between local cache and server snapshot) is the same pattern — interviewers expect you to short-circuit on the first mismatch.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.