Skip to main content

11. Same Tree

easyAsked at Palantir

Given the roots of two binary trees p and q, write a function to check if they are the same. Palantir asks this to verify that you reason about tree equality recursively the same way they compare two versions of an ontology snapshot during a Foundry branch merge.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE phone screen — reported alongside an ontology-diff follow-up.
  • LeetCode Discuss (2025-09)— Tagged as a Palantir warm-up before a deeper tree problem.

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: Same values but structurally different.

Example 3

Input
p = [1,2,1], q = [1,1,2]
Output
false

Approaches

1. Recursive structural compare

Walk both trees in lockstep; both null is true, one null is false, otherwise check value and recurse left+right.

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: Cleanest but can stack-overflow on a skewed tree of depth >10k — Palantir interviewers will probe this.

2. Iterative BFS with paired queue

Enqueue (p, q) pairs; on each pop compare null-ness and value, then enqueue (p.left, q.left) and (p.right, q.right).

Time
O(n)
Space
O(n) queue
function isSameTree(p, q) {
  const queue = [[p, q]];
  while (queue.length) {
    const [a, b] = queue.shift();
    if (!a && !b) continue;
    if (!a || !b) return false;
    if (a.val !== b.val) return false;
    queue.push([a.left, b.left]);
    queue.push([a.right, b.right]);
  }
  return true;
}

Tradeoff: Survives arbitrarily deep trees because the queue lives on the heap. Slightly more code, but production-safe.

Palantir-specific tips

Palantir interviewers grade this on whether you handle the four boundary cases explicitly (both null, one null, value mismatch, full match) before recursing. Bonus signal: explain that the same recursive shape is used to diff two ontology branches in Foundry, where structural plus value equality determines whether a downstream pipeline rebuilds. Mention the iterative version proactively if the interviewer mentions production code.

Common mistakes

  • Returning true on the first matching value without recursing into both children — easy off-by-one when only one subtree matches.
  • Treating (null, null) as falsey because of the !p || !q check ordering.
  • Comparing by JSON.stringify — works but blows up memory and skips early termination.

Follow-up questions

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

  • Symmetric tree (LC 101) — same logic but mirror.
  • Subtree of another tree (LC 572) — call isSameTree at every node.
  • Diff two ontology graphs (DAG, not tree) — what changes?

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 not just serialize both trees and compare strings?

It works but is wasteful: you allocate O(n) string memory and lose early termination. Recursive compare returns false the instant it spots a divergence.

How does this generalize to comparing two DAGs?

Trees have unique paths, so structural recursion suffices. For DAGs, you'd hash subgraphs (e.g., Merkle DAG) to compare in O(n) without exponential repeated traversal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →