Skip to main content

10. Same Tree

easyAsked at Salesforce

Determine if two binary trees are identical in structure and value. Salesforce uses this to test recursive tree comparison, which underlies their metadata-diff and config-deployment pipelines.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce DX team uses tree-diff as a daily pattern for sandbox-to-prod compares.
  • Reddit r/cscareerquestions (2025-11)— Asked on Salesforce intern 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.

Example 3

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

Approaches

1. Serialize and compare strings

Serialize both trees to strings (e.g., preorder with null markers) and compare.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  const serialize = (n) => n ? `${n.val},${serialize(n.left)},${serialize(n.right)}` : 'null';
  return serialize(p) === serialize(q);
}

Tradeoff: Works but allocates O(n) strings. Salesforce prefers direct recursion.

2. Recursive structural comparison

Both null = true. One null = false. Same value AND same left subtree AND same right subtree.

Time
O(n)
Space
O(h)
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 mismatch. JavaScript's && lazy evaluation means you stop as soon as any branch fails.

Salesforce-specific tips

Salesforce uses tree-diff in their CI/CD pipeline to detect metadata changes between sandbox and production. They grade on whether you handle the both-null and one-null cases explicitly. Bonus signal: mention how to extend this for fuzzy matching (e.g., 'subtree equality up to depth k').

Common mistakes

  • Returning true when only one of p/q is null — gives a false positive.
  • Comparing references (p === q) instead of values — works for the same node but not for two trees.
  • Forgetting to recurse on BOTH children — only checking left gives wrong results.

Follow-up questions

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

  • Subtree of Another Tree (LC 572).
  • Symmetric Tree (LC 101).
  • Compare trees structurally but allow values to differ by a delta.

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 null first?

Because if both are null, they're equal — but if only one is null, they're not. Order matters: check both-null before one-null.

Is this BFS-able?

Yes, with two queues processed in lockstep. The recursive DFS is cleaner because of the natural symmetric structure.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →