Skip to main content

11. Same Tree

easyAsked at Databricks

Check whether two binary trees are structurally identical with the same values. Databricks uses this to test recursive pattern-matching, which is the same template Catalyst uses to compare query subtrees during optimizer rule application.

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Glassdoor (2025-08)— Databricks Catalyst engineer phone screen warm-up.
  • LeetCode Discuss (2026-Q1)— Asked as a precursor to subtree-matching / plan-equality questions.

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

Serialize each tree (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: Works but allocates two full strings; misses the early-exit opportunity.

2. Recursive structural comparison

Both null -> true. One null -> false. Else val match AND left match AND right match.

Time
O(min(n, m))
Space
O(h) recursion stack
function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  return p.val === q.val
      && isSameTree(p.left, q.left)
      && isSameTree(p.right, q.right);
}

Tradeoff: Short-circuits on first difference. The && chain saves work — only descends if val matches.

Databricks-specific tips

Databricks engineers reach for this pattern when comparing query subtrees during optimizer rules (e.g., common subexpression elimination). The bonus signal is articulating that this is canonical structural recursion: 'base cases first, then val match, then descend.' Volunteer that early-exit via short-circuit && saves significant work in the common case where trees differ near the root.

Common mistakes

  • Comparing object identity (p === q) instead of structural — that's reference equality, which only works for the same node.
  • Forgetting the (!p && !q) base case — recursing into null crashes.
  • Checking length/size first — for unbalanced trees that's an O(n) precheck that the recursion already does for free.

Follow-up questions

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

  • Subtree of Another Tree (LC 572).
  • Compare query plans for equivalence ignoring expression aliases.
  • Add tolerance for floating-point node values (within epsilon).

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

If both are null, the trees match here. If exactly one is null, they don't. Without the second check, you'd dereference a null pointer.

How does this scale to query-plan equality?

Same recursive shape: compare node type, compare children pairwise. Catalyst's QueryPlan.sameResult uses this pattern with semantic checks added (e.g., aliases ignored).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →