Skip to main content

7. Same Tree

easyAsked at Notion

Determine whether two binary trees are structurally and value-wise identical. Notion uses this to introduce the dual-recursion pattern needed for CRDT operation comparison.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this as a warm-up before tree-diff problems.
  • LeetCode Discuss (2025)— Cited in Notion phone screens.

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 even though values match.

Approaches

1. Serialize both and compare strings

Serialize each tree with null markers and compare.

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

Tradeoff: Correct but allocates the full serialization. The direct DFS is cleaner.

2. Dual DFS recursion (optimal)

Walk both trees in lock-step. Both null = match; one null = mismatch; values differ = mismatch; else recurse on both 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: Six lines, early-exits on first mismatch. The recursion is the proof.

Notion-specific tips

Notion grades the cleanliness of the base-case order: both-null first, then either-null, then value mismatch. Mention that this pattern (lock-step recursion on two structures) is exactly how a CRDT diff engine compares document trees.

Common mistakes

  • Returning true too early — forgetting to recurse on children.
  • Checking value before checking nullness — null.val throws.
  • Confusing structure equality with value equality — different nulls means different structure.

Follow-up questions

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

  • Symmetric Tree (LC 101).
  • Subtree of Another Tree (LC 572) — calls Same Tree as a subroutine.
  • Tree diff: return the list of nodes that differ.

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 three base cases?

Both null is the success terminator; one null distinguishes structure difference; value mismatch shortcuts the recursion.

Could I do this iteratively?

Yes — push pairs (p, q) onto a stack and process them. Same O(n) time, but more bookkeeping.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →