Skip to main content

10. Same Tree

easyAsked at Asana

Given two binary trees, determine if they are structurally identical. Asana asks this to test recursive base cases on trees — a foundation for their structural-diff logic in project templates.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Asana loops.

  • Glassdoor (2026-Q1)— Asana phone-screen tree warmup.

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

Example 3

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

Approaches

1. Serialize and compare

Convert both trees to strings via DFS with null markers; compare strings.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  const ser = (n) => !n ? '#' : `${n.val},${ser(n.left)},${ser(n.right)}`;
  return ser(p) === ser(q);
}

Tradeoff: Works but allocates O(n) string. Recursive comparison is cleaner.

2. Recursive structural comparison

Both null -> true. One null -> false. Different val -> false. Else recurse on subtrees.

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: Short-circuits on mismatch, returns early. The four-case structure (both null, one null, val mismatch, recurse) is the canonical pattern.

Asana-specific tips

Asana wants the four-case structure stated explicitly before you code — they grade on clear case analysis. If you blur 'one null' and 'val mismatch' into one case, the bug becomes hard to spot under pressure.

Common mistakes

  • Forgetting the 'one null, one not' case — leads to a null-pointer crash.
  • Using == instead of === in JS — accidental coercion.
  • Comparing references (p === q) — only works when nodes are aliased.

Follow-up questions

An interviewer at Asana may pivot to one of these next:

  • Symmetric Tree (LC 101) — same problem with one tree mirrored.
  • Subtree of Another Tree (LC 572).
  • What if the trees can have cycles?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Can you do this iteratively?

Yes — push both roots onto a queue/stack as pairs. Each pop pulls a pair, checks the same four cases, and pushes children as pairs.

What if values are objects, not primitives?

You'd need a deep-equality function. The structural recursion is the same — only the leaf comparison changes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →