Introduction to the Same Tree Problem
The "Same Tree" problem is one of the foundational challenges you will encounter when studying binary trees and recursion. It appears frequently in coding interviews, competitive programming platforms like LeetCode, and computer science coursework. At its core, the problem asks a simple question: given two binary trees, determine whether they are structurally identical and contain the same values at every corresponding node.
While the problem statement is short, mastering it teaches you several important concepts: tree traversal, recursive thinking, base case design, and edge case handling. In this tutorial, we will walk through everything you need to know to solve the Same Tree problem in JavaScript, from understanding the data structure to writing clean, efficient, production-ready code.
What Is a Binary Tree?
Before diving into the solution, let us quickly recap what a binary tree is. A binary tree is a hierarchical data structure where each node has at most two children, typically referred to as the left child and the right child. In JavaScript, we usually represent a tree node using a simple class or object literal.
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
With this structure in place, we can build trees by chaining nodes together. Understanding this representation is essential because every solution to the Same Tree problem depends on comparing these nodes systematically.
Understanding the Same Tree Problem
The formal definition of the Same Tree problem is straightforward. Two binary trees are considered the same if they are structurally identical and all corresponding nodes have the same value. This means that not only must the values match, but the shape of the trees must also match exactly.
For example, consider these two trees:
// Tree A
// 1
// / \
// 2 3
const treeA = new TreeNode(1,
new TreeNode(2),
new TreeNode(3)
);
// Tree B
// 1
// / \
// 2 3
const treeB = new TreeNode(1,
new TreeNode(2),
new TreeNode(3)
);
These two trees are the same. However, if Tree B had its right child missing, or if any value differed, the trees would not be considered the same.
Why This Problem Matters
You might wonder why such a seemingly simple problem deserves so much attention. There are several reasons:
- Recursion practice: It is one of the cleanest examples of recursive problem-solving on a non-linear data structure.
- Interview frequency: It is a common warm-up question in technical interviews at major tech companies.
- Foundation for harder problems: Many advanced tree problems, such as subtree checking or tree serialization, build on the same recursive comparison logic.
- Edge case awareness: It forces you to think carefully about null nodes, empty trees, and asymmetric structures.
Solving Same Tree Recursively
The most natural and elegant way to solve the Same Tree problem is through recursion. The idea is to compare the current nodes of both trees, then recursively compare their left subtrees and right subtrees. If all comparisons return true, the trees are the same.
The Recursive Algorithm
Here is the step-by-step logic:
- If both nodes are null, return true. Two empty trees are identical.
- If only one of the nodes is null, return false. The structures differ.
- If the values of the two nodes differ, return false.
- Recursively compare the left children and the right children.
Let us translate this into JavaScript code:
function isSameTree(p, q) {
// Base case: both nodes are null
if (p === null && q === null) {
return true;
}
// One node is null, the other is not
if (p === null || q === null) {
return false;
}
// Values differ
if (p.val !== q.val) {
return false;
}
// Recursively compare left and right subtrees
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
This solution is concise and readable. Each base case handles a specific scenario, and the recursive case breaks the problem down into smaller subproblems. Let us test it with a few examples.
Testing the Recursive Solution
// Example 1: Identical trees
const tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const tree2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(isSameTree(tree1, tree2)); // true
// Example 2: Different structure
const tree3 = new TreeNode(1, new TreeNode(2), null);
const tree4 = new TreeNode(1, null, new TreeNode(2));
console.log(isSameTree(tree3, tree4)); // false
// Example 3: Different values
const tree5 = new TreeNode(1, new TreeNode(2), new TreeNode(1));
const tree6 = new TreeNode(1, new TreeNode(1), new TreeNode(2));
console.log(isSameTree(tree5, tree6)); // false
// Example 4: Both empty
console.log(isSameTree(null, null)); // true
All four examples produce the expected results, confirming that our recursive solution handles the common cases correctly.
Complexity Analysis
Understanding the time and space complexity of your solution is crucial, especially in interview settings. Let us analyze the recursive approach.
Time Complexity
The time complexity is O(n), where n is the number of nodes in the smaller of the two trees. In the worst case, we visit every node in both trees exactly once. If the trees differ early, the algorithm short-circuits and returns false without visiting all nodes, but the worst-case bound remains linear.
Space Complexity
The space complexity is O(h), where h is the height of the tree. This space is consumed by the call stack due to recursion. In a balanced tree, h is approximately log(n), giving us O(log n) space. In the worst case, where the tree is essentially a linked list, h equals n, giving us O(n) space.
Solving Same Tree Iteratively
While recursion is elegant, some environments have strict call stack limits, and some interviewers prefer iterative solutions. We can solve the Same Tree problem iteratively using a queue or a stack to perform a breadth-first or depth-first traversal simultaneously on both trees.
Iterative Approach Using a Queue
The idea is to enqueue pairs of corresponding nodes from both trees. At each step, we dequeue a pair, compare their values, and enqueue their children. If at any point the comparison fails, we return false.
function isSameTreeIterative(p, q) {
const queue = [[p, q]];
while (queue.length > 0) {
const [node1, node2] = queue.shift();
// Both null - continue
if (node1 === null && node2 === null) {
continue;
}
// One null, one not - different structure
if (node1 === null || node2 === null) {
return false;
}
// Different values
if (node1.val !== node2.val) {
return false;
}
// Enqueue children pairs
queue.push([node1.left, node2.left]);
queue.push([node1.right, node2.right]);
}
return true;
}
This iterative version produces the same results as the recursive solution but avoids potential stack overflow issues on very deep trees. The time complexity remains O(n), and the space complexity is O(n) in the worst case due to the queue storage.
Iterative Approach Using a Stack
If you prefer depth-first traversal, you can replace the queue with a stack. The logic is nearly identical, only the order of traversal changes.
function isSameTreeDFS(p, q) {
const stack = [[p, q]];
while (stack.length > 0) {
const [node1, node2] = stack.pop();
if (node1 === null && node2 === null) {
continue;
}
if (node1 === null || node2 === null) {
return false;
}
if (node1.val !== node2.val) {
return false;
}
stack.push([node1.left, node2.left]);
stack.push([node1.right, node2.right]);
}
return true;
}
Both iterative approaches are valid. The choice between queue and stack depends on whether you want breadth-first or depth-first traversal behavior, though for correctness, either works fine.
Edge Cases to Consider
When solving tree problems, edge cases are where bugs tend to hide. Here are the scenarios you should always test:
- Both trees are null: Should return true.
- One tree is null, the other is not: Should return false.
- Trees with a single node: Compare the single values.
- Trees with identical values but different structures: Should return false.
- Very deep trees: Test for stack overflow with recursion.
- Trees with negative or zero values: Ensure value comparison handles all numeric cases.
Writing tests for these cases will give you confidence that your solution is robust.
Best Practices
Now that we have covered the core solutions, let us discuss some best practices to keep in mind when implementing and presenting your solution.
Choose Readability Over Cleverness
It can be tempting to write a one-liner using logical operators, but clarity should always come first. The explicit base-case approach is easier to debug, explain, and maintain. Avoid overly terse code unless you are in a competitive programming context where brevity matters.
Handle Null Checks Early
Always check for null nodes before accessing properties like val, left, or right. Failing to do so will result in runtime errors. The pattern of checking both-null first, then one-null, is a reliable way to structure these checks.
Use Strict Equality
When comparing node values, use strict equality (===) rather than loose equality (==). This prevents unexpected type coercion bugs, especially if your tree might contain mixed types.
Consider Iterative Solutions for Deep Trees
If you know your trees could be very deep, prefer the iterative approach to avoid call stack limits. JavaScript engines typically have a maximum call stack depth, and exceeding it will throw a "Maximum call stack size exceeded" error.
Write Tests
Always write tests for your tree functions. Even a small set of test cases covering the edge cases mentioned earlier will catch most bugs. Here is a simple test harness you can use:
function testIsSameTree(fn) {
const assert = (condition, message) => {
console.assert(condition, message);
if (!condition) process.exitCode = 1;
};
assert(fn(null, null) === true, "Both null should be true");
assert(fn(new TreeNode(1), null) === false, "One null should be false");
assert(
fn(new TreeNode(1, new TreeNode(2)), new TreeNode(1, new TreeNode(2))) === true,
"Identical trees should be true"
);
assert(
fn(new TreeNode(1, new TreeNode(2)), new TreeNode(1, null, new TreeNode(2))) === false,
"Different structure should be false"
);
console.log("All tests completed.");
}
testIsSameTree(isSameTree);
testIsSameTree(isSameTreeIterative);
testIsSameTree(isSameTreeDFS);
Common Mistakes to Avoid
Even experienced developers make mistakes when solving tree problems. Here are some common pitfalls and how to avoid them.
Forgetting the Both-Null Base Case
If you forget to check whether both nodes are null before checking individual nulls, your function may incorrectly return false for two empty subtrees. Always handle the both-null case first.
Comparing Only Values
A common beginner mistake is to compare only the values of the root nodes and ignore the structure. Remember, two trees are the same only if both their values and structures match.
Not Short-Circuiting
In the recursive solution, using the logical AND operator (&&) ensures that if the left subtree comparison returns false, the right subtree comparison is skipped. This short-circuit behavior improves performance. If you store the results in variables and compare them separately, you lose this optimization.
Extending the Solution
Once you understand the Same Tree problem, you can apply the same principles to related problems. Here are a few extensions worth exploring.
Symmetric Tree
A tree is symmetric if its left and right subtrees are mirror images of each other. You can adapt the Same Tree solution by comparing the left child of one subtree with the right child of the other.
function isMirror(t1, t2) {
if (t1 === null && t2 === null) return true;
if (t1 === null || t2 === null) return false;
return (
t1.val === t2.val &&
isMirror(t1.left, t2.right) &&
isMirror(t1.right, t2.left)
);
}
function isSymmetric(root) {
if (root === null) return true;
return isMirror(root.left, root.right);
}
Subtree of Another Tree
This problem asks whether one tree is a subtree of another. You can use the Same Tree function as a helper to check if any subtree of the larger tree matches the smaller tree.
function isSubtree(root, subRoot) {
if (root === null) return subRoot === null;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
These extensions demonstrate how mastering the Same Tree problem opens the door to solving a whole family of tree-related challenges.
Conclusion
The Same Tree problem is a deceptively simple challenge that reinforces essential skills in recursion, tree traversal, and careful edge case handling. By comparing nodes systematically, checking for null cases early, and choosing between recursive and iterative approaches based on your constraints, you can write clean and efficient solutions in JavaScript. Whether you are preparing for an interview or building a foundation for more advanced tree algorithms, the patterns you learn here will serve you across countless related problems. Practice the code examples, test against the edge cases, and try the extensions to deepen your understanding of binary trees.