Skip to main content

10. Same Tree

easyAsked at Adobe

Given two binary trees, decide if they are structurally identical and have the same node values. Adobe uses this to test whether you can write clean structural recursion — the foundation for diffing two versions of a document tree in collaborative editing.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe Document Cloud interview reports cite this warm-up.
  • LeetCode Discuss (2025-07)— Adobe SDE-I rounds frequently include this.

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 both trees as strings with null markers, compare.

Time
O(n + m)
Space
O(n + m)
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: Works but allocates strings — wasteful for hot-path diffing. Mention as a stepping stone.

2. Recursive structural compare

Both null → true. One null → false. Otherwise val + recurse left + recurse right.

Time
O(min(n, m))
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: Short-circuits on first mismatch. Linear in the smaller tree because we stop at the first divergence. Adobe interviewers love this exact structure as a baseline for tree-diff.

Adobe-specific tips

Adobe interviewers — particularly on the InDesign or document teams — see this as a stepping stone to tree-diff algorithms. Mention that this structural comparison is what backs change detection in collaborative document editing, where two clients reconcile their DOM versions. Bonus signal: discuss how this scales when nodes have many children (general tree, not binary).

Common mistakes

  • Checking val before null — crashes when one is null.
  • Returning true on partial subtree match — both must match completely.
  • Forgetting to short-circuit — wastes time after first mismatch.

Follow-up questions

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

  • Symmetric Tree (LC 101).
  • Subtree of Another Tree (LC 572).
  • How would you parallelize this for huge trees?

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 check both nulls first?

Two null nodes are 'the same' (empty subtree matches empty subtree). Checking that first lets you handle the base case before any null-dereference.

Can I make this iterative?

Yes — push pairs of nodes onto a stack and pop in lockstep. Same time complexity, heap-allocated stack, safer for deep trees.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →