Skip to main content

11. Same Tree

easyAsked at Workday

Given two binary trees, determine if they are structurally identical with equal values. Workday uses this to test parallel recursion — diffing two snapshots of an org chart to find structural drift.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday org-chart team SDE2 phone.

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

DFS-serialize each tree to a string with null markers, then compare.

Time
O(n)
Space
O(n)
function ser(n){ if(!n) return '#'; return n.val+','+ser(n.left)+','+ser(n.right); }
return ser(p) === ser(q);

Tradeoff: O(n) memory for two string buffers. Works but wasteful.

2. Parallel DFS

Recurse both trees in lockstep. Mismatch at structure or value -> false.

Time
O(n)
Space
O(h) recursion
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 at the first mismatch. No extra memory.

Workday-specific tips

Workday grades for the 'both null' base case AND the 'one null, other not' early return — confusing the two is the classic bug. Mention org-chart drift detection as the use case; they'll appreciate the domain hook.

Common mistakes

  • Forgetting the 'both null = true' base case — recursion never terminates correctly on equal subtrees.
  • Checking p.val === q.val before the null checks — null.val crashes.
  • Using == instead of === — surprising NaN issues.

Follow-up questions

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

  • Symmetric Tree (LC 101) — same structure, mirror version.
  • Subtree of Another Tree (LC 572).
  • What if values are floats with epsilon tolerance?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Can I do this iteratively?

Yes — use a queue of (p, q) pairs. Same logic, BFS instead of DFS.

Why three null checks (both null, p null, q null)?

The 'both null' base case returns true (equal). The 'one null' check returns false. Combining them into one check breaks the equality case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →