10. Same Tree

Q: Why check structure, not just inorder?

Two trees can produce the same inorder list with different structure. The co-recursive walk locks both shape and values.

Q: What's the short-circuit benefit?

If the roots differ, we return false in O(1) without touching the subtrees. For nearly-equal large trees this means a single comparison vs. O(n) work.

easyAsked at Plaid

Check if two binary trees are identical in structure and values. Plaid asks this as a baseline for harder tree-equality problems like checking whether two transaction-category snapshots match.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE I screen.
LeetCode Discuss (2026)— Reported as Plaid 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

Explanation: Different structure.

Approaches

1. Serialize both, compare strings

Convert each tree to a canonical preorder string with explicit nulls, compare.

Time: O(n)
Space: O(n)

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

Tradeoff: Works but allocates strings. Bigger trees pay for the concatenation.

2. Co-recursive walk

Recurse on both trees simultaneously. Bail early on the first mismatch.

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: Linear time, short-circuits on first mismatch — important when most trees are equal. Cleaner than serialization.

Plaid-specific tips

Plaid grades this on whether you bail on the first mismatch rather than walking the whole tree. Bonus signal: mention how this generalizes to comparing two category-tree snapshots in their ETL — the short-circuit is critical when 99% of webhook bodies arrive unchanged.

Common mistakes

Only checking values, not structure — [1,2] and [1,null,2] are different trees.
Forgetting the both-null base case.
Using == instead of === when values could be 0 — fine in JS for numbers but a code-review red flag.

Follow-up questions

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

Symmetric tree (LC 101) — same trick, mirrored recursion.
Subtree of another tree (LC 572).
Generalize to N-ary trees for multi-child category hierarchies.

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 structure, not just inorder?

Two trees can produce the same inorder list with different structure. The co-recursive walk locks both shape and values.

What's the short-circuit benefit?

If the roots differ, we return false in O(1) without touching the subtrees. For nearly-equal large trees this means a single comparison vs. O(n) work.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →