Skip to main content

10. Same Tree

easyAsked at Intuit

Given two binary trees, determine whether they are structurally identical with equal node values. Intuit asks this in form-comparison contexts — TurboTax verifies that a saved form-rule tree matches the canonical template.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2025-12)— TurboTax form-engine SWE screen.
  • LeetCode Discuss (2026-Q1)— Intuit phone-screen.

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

Serialize each tree to a string with nulls, compare strings.

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

Tradeoff: Allocates strings; subtle bug if not separating values with delimiters (e.g., 12 vs 1,2).

2. Recursive structural compare (optimal)

Both null → true. One null → false. Otherwise values equal AND left subtrees same AND right subtrees same.

Time
O(n)
Space
O(h) recursion stack
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: Clean and short-circuits via && — stops on first mismatch.

Intuit-specific tips

Intuit grades this on three null-check cases (both null, one null, neither null) — many candidates miss the 'one null' case and get tripped up by structural differences like [1,2] vs [1,null,2]. Bonus signal: discuss how this generalizes to tax-form-rule trees where each node has a question + child rules.

Common mistakes

  • Forgetting the 'one is null, the other isn't' case — silently returns true.
  • Comparing only values, not structure — [1,2] and [1,null,2] both contain values {1,2} but differ structurally.
  • Stack-overflow on extremely deep degenerate trees — switch to iterative BFS with two queues.

Follow-up questions

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

  • Symmetric Tree (LC 101) — same-tree variant against the mirror.
  • Subtree of Another Tree (LC 572) — same-tree at every position.
  • Check that a saved tax-form rule tree matches the canonical version.

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 short-circuit with &&?

If a subtree differs, no need to compare the other subtree — saves work on average-case mismatched trees.

Recursive vs iterative?

Recursive is shorter and idiomatic. Iterative (two queues / two stacks in lockstep) avoids stack-overflow on adversarial inputs. Have both ready.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →