Same Tree: Comparing Two Binary Trees with Recursive DFS
How to check if two binary trees are identical with recursive DFS — the base cases, JavaScript code, a worked walkthrough, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Same Tree looks trivial until you try to write it cleanly: given two binary trees, decide whether they are the same. Not similar, not the same set of values — the same. Identical shape, identical value at every corresponding position.
The reason it earns its spot in every interview prep list is that it teaches the cleanest possible template for structural recursion on two trees at once. You walk both trees in lockstep, and at each pair of nodes you ask three tiny questions. Get those three questions and their order right, and the whole solution is nine lines. Get them wrong and you'll return true for trees that clearly differ.
This exact "compare two trees node by node" skeleton is the backbone of Symmetric Tree, Subtree of Another Tree, and Merge Two Binary Trees — so it pays to internalize it here.
The problem
You're given the roots of two binary trees, p and q. Return true if they are structurally identical and every corresponding node has the same value. Otherwise return false.
Two things must match: the shape (wherever one tree has a node, the other must have a node too) and the values (matching positions must hold equal numbers).
Tree p: 1 Tree q: 1
/ \ / \
2 3 2 4
Input: p = [1,2,3], q = [1,2,4]
Output: false // roots match, left leaves match, but 3 !== 4 on the rightIf instead q = [1,2,3], the answer is true. And two empty trees (p = [], q = []) are trivially the same, which turns out to be an important edge case.
The brute force baseline
A tempting shortcut is to serialize each tree into a string — say, a pre-order traversal with explicit null markers — and compare the two strings.
function isSameTree(p, q) {
const serialize = (node) => {
if (node === null) return "#";
return `(${node.val} ${serialize(node.left)} ${serialize(node.right)})`;
};
return serialize(p) === serialize(q);
}This works and is genuinely useful when you need to compare one tree against many others (cache the string once, compare cheaply). But for a single comparison it's wasteful: you build two full strings in memory, walking every node of both trees even when the roots already differ, then do an O(n) string comparison on top. The null markers are also easy to get wrong — drop them and [1,2] serializes the same as [1,null,2], silently returning true for two different shapes.
The key insight: recurse on both trees in parallel
You don't need strings. Compare the two trees the same way you'd compare them by eye: line up the roots, then line up the left subtrees, then the right subtrees.
At any pair of nodes (p, q) there are exactly three outcomes to check, in order:
- Both null → this branch matched all the way down. Return
true. - Exactly one null → one tree has a node the other doesn't. Structures differ. Return
false. - Both non-null but values differ → return
false.
If none of those three fired, the current nodes agree, so the trees are the same here — and the whole answer reduces to: do the left subtrees match and do the right subtrees match? That's the same function called on smaller inputs. The recursion carries the base cases; you never write an explicit loop.
The order matters. Checking "both null" before "one null" is what lets the second check assume that if you reached it, at least one node is non-null.
The optimal solution
This is the exact algorithm the Same Tree visualizer steps through:
function isSameTree(p, q) {
if (p === null && q === null) {
return true;
}
if (p === null || q === null) {
return false;
}
if (p.val !== q.val) {
return false;
}
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}Read it as the three gates followed by the recursive step. The && is doing real work: short-circuit evaluation means if the left subtrees don't match, isSameTree(p.right, q.right) is never even called — the function bails the moment it finds any disagreement.
Every node of the trees is visited at most once, and the work at each node is a couple of comparisons, so this is as fast as tree comparison can be.
Walkthrough
Trace p = [1,2,3], q = [1,2,4]. Each row is one call to isSameTree, showing which gate it hits. Indentation mirrors the call depth.
| Call | p.val, q.val | Gate hit | Returns |
|---|---|---|---|
isSameTree(1, 1) | 1, 1 | all gates pass → recurse | pending |
→ isSameTree(2, 2) | 2, 2 | all gates pass → recurse | pending |
→ → isSameTree(null, null) | –, – | both null | true |
→ → isSameTree(null, null) | –, – | both null | true |
→ isSameTree(2, 2) resolves | true && true | true | |
→ isSameTree(3, 4) | 3, 4 | values differ (3 ≠ 4) | false |
isSameTree(1, 1) resolves | true && false | false |
The left subtree (2 vs 2, with two null children each) fully matches and returns true. Then the right comparison hits 3 !== 4 and returns false. Back at the root, true && false is false, and because of short-circuiting nothing further is explored. Final answer: false.
Notice the call stack never got deeper than three frames — the recursion depth equals the height of the trees, not the number of nodes.
Complexity
Let n be the number of nodes in the smaller tree (once one side runs out, a one null or both null gate ends that branch).
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Each corresponding node pair is compared exactly once; O(1) work per pair |
| Space | O(h) | Recursion stack holds one frame per level, where h is the tree height |
Space is O(h), not O(n): a balanced tree gives O(log n) stack depth, while a degenerate "linked-list" tree (every node has one child) pushes it to O(n). There's no auxiliary data structure — the only memory cost is the call stack.
Common mistakes
- Wrong base-case order. If you test
p.val !== q.valbefore the null checks, you'll dereferencenull.valand crash the instant one tree is shorter than the other. Null checks first, always. - Collapsing the two null checks into one. Writing
if (p === null || q === null) return p === qis a clever one-liner but subtle; keeping "both null → true" and "one null → false" as separate, ordered gates is clearer and harder to break. - Only comparing values, forgetting structure. Two trees can hold the same multiset of values in different shapes.
[1,2]and[1,null,2]share values but differ in structure — theone nullgate is what catches this. - Serializing without null markers. As noted above, omitting explicit
nullsentinels makes distinct shapes serialize identically, producing false positives. - Returning after only the left recursion. You must
&&both subtree results. ReturningisSameTree(p.left, q.left)alone ignores everything on the right.
Where this pattern shows up next
The "walk two trees in lockstep, three gates per node" template generalizes directly:
- Symmetric Tree — the same comparison, but a tree against its own mirror, so you pair
left.leftwithright.right. - Symmetric Tree - Iterative — the mirror check rebuilt with an explicit queue instead of recursion, useful when stack depth is a concern.
- Subtree of Another Tree — calls this exact
isSameTreelogic at every node of a larger tree to test containment. - Subtree of Another Tree (Serialization) — the string-comparison approach from our baseline, done properly with delimiters and null markers.
You can also step through Same Tree interactively to watch the two trees light up node by node as the recursion descends and unwinds.
FAQ
What is the time complexity of the Same Tree solution?
O(n) time, where n is the number of nodes in the smaller tree. Each pair of corresponding nodes is visited once and does constant work — a couple of comparisons — before recursing. Space is O(h), the height of the tree, because the recursion stack holds one frame per level: O(log n) for a balanced tree and O(n) for a fully skewed one.
Why do the null checks come before the value check?
Because the value check reads p.val and q.val, and reading .val on a null node throws. The "both null" gate returns early for matched empty branches, and the "one null" gate catches structural differences — only after both fire is it safe to assume p and q are real nodes with values to compare. Reordering these gates crashes the moment the two trees have different shapes.
Can I solve Same Tree iteratively instead of recursively?
Yes. Push the pair (p, q) onto a stack or queue, then repeatedly pop a pair and apply the same three checks; on a match, push the (left, left) and (right, right) child pairs. It produces identical results and avoids deep recursion, which matters if the tree could be tall enough to overflow the call stack. The recursive version is shorter and usually preferred in interviews for clarity.
How is Same Tree different from Symmetric Tree?
Same Tree compares two separate trees position for position: p.left against q.left. Symmetric Tree checks whether a single tree is a mirror of itself, so it compares left.left against right.right and left.right against right.left — the recursion crosses sides. The node-level machinery (three gates, recurse, &&) is identical; only which children you pair up changes.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.