Skip to main content

11. Same Tree

easyAsked at Coinbase

Determine 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 Alex Chen, 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

Input
p = [1,2,3], q = [1,2,3]
Output
true

Example 2

Input
p = [1,2], q = [1,null,2]
Output
false

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Same Tree and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →