Skip to main content

13. Same Tree

easyAsked at Square

Check whether two binary trees are structurally identical and have equal values. Square uses this to validate that you can write symmetric recursion — same instinct they want when comparing two replicas of an inventory tree during offline sync conflict resolution.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • Glassdoor (2025)— Square POS phone screen tree-warmup.
  • LeetCode Discuss (2026)— Cash App backend onsite.

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 both, compare strings

Pre-order serialize with null markers and compare.

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: Cute one-liner but allocates a string proportional to tree size; Square interviewers prefer the direct recursion.

2. Synchronous recursion

Walk both trees in lockstep. Match if both null, or both non-null with equal val and matching 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: Early exit on first mismatch. Short-circuit && skips the right subtree when left already mismatches.

Square-specific tips

Square interviewers grade this on whether you order the base cases correctly: both-null first (success), then exactly-one-null (mismatch), THEN value compare. Inverting that order leads to null-deref bugs. Mention the early-exit on the first false — Square cares about not wasting cycles in their high-throughput batch jobs.

Common mistakes

  • Checking value before nullability — crashes on null.val.
  • Returning the recursive call's result without && — both subtrees must match.
  • Treating [1, null, 2] and [1, 2] as identical.

Follow-up questions

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

  • Subtree of another tree (LC 572).
  • Symmetric tree (LC 101) — same logic, mirrored.
  • Tree isomorphism (children can be in any order).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why both-null is the first check?

If you check exactly-one-null first, the both-null case takes the false branch incorrectly. Always handle the symmetric base case first.

Is this O(n) on the smaller tree?

It's O(min(n_p, n_q)) when one side mismatches early. Worst case (identical) it's O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →