Skip to main content

10. Same Tree

easyAsked at PayPal

Given two binary trees, decide if they are structurally identical and the nodes have the same values. PayPal asks this as a recursion warm-up — the same shape used when diffing two snapshots of a transaction-state tree to detect tampering or replay.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Blind (2025-12)— PayPal SDE-1, simple recursion check.

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 trees and compare strings

Pre-order serialize each tree to a string with explicit nulls, then compare.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  function ser(n) {
    if (!n) return 'X';
    return n.val + ',' + ser(n.left) + ',' + ser(n.right);
  }
  return ser(p) === ser(q);
}

Tradeoff: Works but allocates two big strings. Wasteful when trees diverge at the root.

2. Recursive parallel walk (optimal)

Walk both trees in lockstep. If both null, equal. If one null, unequal. Else compare values + recurse on children.

Time
O(min(n, m))
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 first mismatch. Same pattern PayPal uses for streaming tree-diff in fraud-replay detection — bail at the first divergence.

PayPal-specific tips

PayPal grades you on the short-circuit: the `&&` in the return means a left-subtree mismatch never walks the right subtree. Mention this for production-style transaction-tree diff where you stop the instant tampering is detected. Avoid the serialize approach in interviews — it's a code smell.

Common mistakes

  • Forgetting the `(!p && !q)` base — both-null is equal, not unequal.
  • Using `==` instead of `===` — fine in JS for null comparisons but a habit worth breaking.
  • Comparing serialized strings without null markers — [1,2] and [1,null,2] would falsely match.

Follow-up questions

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

  • Symmetric Tree (LC 101) — check if a tree is a mirror of itself.
  • Subtree of Another Tree (LC 572) — same problem applied at every node of t.
  • What if values are floats — precision tolerance?

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 check `(!p || !q)` after `(!p && !q)`?

If we reach this line, we know at least one is non-null. The `||` then tells us exactly one is null, so they differ in structure.

Does this work iteratively?

Yes — push pairs of nodes onto a stack and compare in a loop. Useful if recursion depth concerns you.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →