11. Same Tree
easyAsked at WorkdayGiven 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 Sam K., 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
p = [1,2,3], q = [1,2,3]trueExample 2
p = [1,2], q = [1,null,2]falseExample 3
p = [1,2,1], q = [1,1,2]falseApproaches
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.
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.