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 Sam K., 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).

More Databricks coding interview questions

See all Databricks problems →

Companies that also ask Same Tree