10. Same Tree
easyAsked at SnowflakeDetermine whether two binary trees are structurally identical and have the same values. Snowflake asks this as a recursion warm-up before deeper tree problems, often paired with a structural-equality follow-up on query plans.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Snowflake loops.
- Glassdoor (2025-Q4)— Snowflake compiler team uses this to set up plan-equality follow-up.
- LeetCode Discuss (2025-08)— Reported at Snowflake new-grad screens.
Problem
Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Constraints
The number of nodes in both trees is in the range [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]falseExample 3
p = [1,2,1], q = [1,1,2]falseApproaches
1. Serialize and compare strings
Build a canonical string representation of each tree, then compare.
- Time
- O(n)
- Space
- O(n)
function isSameTree(p, q) {
function serialize(n) {
if (!n) return '#';
return `${n.val},${serialize(n.left)},${serialize(n.right)}`;
}
return serialize(p) === serialize(q);
}Tradeoff: Works but allocates O(n) string. Don't ship for large trees.
2. Recursive structural compare (optimal)
Both null -> true. One null -> false. Values differ -> false. Otherwise recurse on left and right.
- 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: Linear, no allocations. Short-circuits on first mismatch.
Snowflake-specific tips
Snowflake interviewers want the short-circuit pattern (return false as soon as you find a difference). Bonus signal: pivot to comparing query plans — discuss how Snowflake's planner hashes plan subtrees for the plan cache, and what hash collisions you'd need to be careful about.
Common mistakes
- Returning true at the leaf without checking that both p AND q are null.
- Comparing only values, missing the structural difference between [1,2] and [1,null,2].
- Trying to flatten the tree and compare arrays — loses structural info.
Follow-up questions
An interviewer at Snowflake may pivot to one of these next:
- Symmetric Tree (LC 101).
- Is one tree a subtree of another (LC 572)?
- How does Snowflake hash plan subtrees for the plan cache?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why not compare arrays of values?
Arrays lose null-children positions. [1,2] and [1,null,2] would both flatten to [1,2] but they're structurally different trees.
How does plan equality work in a query planner?
Snowflake hashes each plan node (operator + child hashes + key arguments) bottom-up. Plans with the same hash are candidates for cache reuse. The shape is exactly this recursive compare.