11. Same Tree
easyAsked at CoinbaseDetermine whether two binary trees are structurally identical with equal values. Coinbase asks this as a warm-up for tree-equivalence and snapshot-comparison follow-ups.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Coinbase loops.
- Glassdoor (2026-Q1)— Coinbase phone-screen warm-up.
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]falseApproaches
1. Serialize both, compare strings
Serialize each tree to a delimited preorder string and compare.
- Time
- O(n)
- Space
- O(n)
function isSameTree(p, q) {
function ser(n) { return n ? n.val + ',' + ser(n.left) + ',' + ser(n.right) : 'N'; }
return ser(p) === ser(q);
}Tradeoff: Works but allocates O(n) strings and is sensitive to delimiter collisions for non-numeric values.
2. Recursive simultaneous walk
Both null → equal. One null → unequal. Else compare values and recurse on both pairs of subtrees.
- Time
- O(n)
- Space
- O(h) recursion
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: Short-circuits at the first mismatch. Clean and idiomatic.
Coinbase-specific tips
Coinbase likes the explicit 3-case structure (both null, one null, value mismatch) — they read it as 'this candidate enumerates failure modes.' Bonus if you mention you'd use this shape to verify a leader and a follower in a replicated order book agree on state.
Common mistakes
- Comparing only values, not structure — [1,2] and [1,null,2] both have value 2 in different positions.
- Using == in languages with reference equality — compare values explicitly.
- Allocating serialized strings instead of recursing.
Follow-up questions
An interviewer at Coinbase may pivot to one of these next:
- Find the first divergence (return a node path).
- What if values are floats with tolerance?
- Iterative version using two stacks or BFS queues.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
What's the iterative version?
Use two queues (or one queue of pairs). Pop both, compare; if either is null, the other must be too. Push left pair and right pair.
Could you hash the subtrees instead?
Yes — Merkle-tree style subtree hashing lets you compare in O(1) after O(n) preprocessing. Used in replicated state systems for fast diff.