Same Tree
Understanding the Problem
We're given two binary trees and need to determine if they're identical. "Identical" here means two things at once: the trees must have exactly the same shape, and every corresponding node must hold the same value.
Comparing two folder structures on a computer is similar. It's not enough that both have the same set of files. The files need to be in the same folders, at the same levels, in the same positions. If one folder has a subfolder on the left and the other has it on the right, they're different, even if the contents are the same.
This definition is recursive: two trees are the same if and only if their root values match, their left subtrees are the same, and their right subtrees are the same. If any of these three conditions fails, the trees differ. That recursive definition translates directly into both approaches below.
Key Constraints:
Number of nodes in [0, 100]→ The trees are small, so a single linear pass over the nodes is more than fast enough. The interesting choice is between recursion and an explicit stack or queue.-10^4 <= Node.val <= 10^4→ Values fit in a 32-bit integer and can be negative, so compare values directly with==. No overflow or hashing concerns.0 nodesis valid → Both trees can be empty. Two empty trees are the same, which is why the all-null case returns true.
Approach 1: Recursive DFS
Intuition
Walk through both trees at the same time, node by node, and check that everything matches at each step.
At any point in the traversal, we hold one node from tree p and one node from tree q. Three cases cover every possibility:
- Both nodes are null. Both subtrees are empty, so they match here. Return true.
- One is null but the other isn't. The structures differ. Return false.
- Neither is null. Compare their values. If the values differ, return false. If they match, recursively check both the left and right children.
Each recursive call applies the same three cases to a smaller pair of subtrees, stopping at the null base cases. If every pair passes without a mismatch, the trees are the same.
Algorithm
- If both
pandqare null, return true. - If only one of
porqis null, return false. - If
p.valdoes not equalq.val, return false. - Recursively check if the left subtrees are the same (
p.left,q.left). - Recursively check if the right subtrees are the same (
p.right,q.right). - Return true only if both recursive calls return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once, where n is the smaller of the two trees' sizes. In the best case (roots differ), we return in O(1).
- Space Complexity: O(h). The recursion stack goes as deep as the tree height. For a balanced tree h = O(log n), for a skewed tree h = O(n).
The recursive approach relies on the call stack, which can overflow on a deeply skewed tree. The next approach replaces that implicit stack with an explicit queue, moving the traversal state onto the heap.
Approach 2: Iterative BFS
Intuition
The comparison logic stays identical to the recursive version. The only change is that an explicit queue manages the traversal order instead of the call stack. We store pairs of nodes (one from each tree) in the queue. For each pair removed from the queue, we apply the same null and value checks. If both nodes match, we enqueue their children as two new pairs.
The structural correspondence is preserved by always pairing left child with left child and right child with right child. A pair (a, b) reaches the queue only after a and b were confirmed to occupy the same position in their respective trees, so comparing them is a valid position-by-position check. The order in which pairs come off the queue does not affect the result: a stack would visit the same pairs in a different order and reach the same answer, because each pair is judged independently.
Algorithm
- Create a queue and add the pair
(p, q)to it. - While the queue is not empty:
- Dequeue a pair of nodes.
- If both are null, continue to the next pair.
- If only one is null, return false.
- If their values differ, return false.
- Enqueue the pair
(node1.left, node2.left). - Enqueue the pair
(node1.right, node2.right). - If we process all pairs without finding a mismatch, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node at most once, where n is the number of nodes in the smaller tree.
- Space Complexity: O(n). The queue can hold up to O(n) nodes in the worst case. For a complete binary tree, the last level has roughly n/2 nodes.