Same Tree
Last Updated: March 29, 2026
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 (same structure), and every corresponding node must hold the same value.
Think of it like comparing two folder structures on your computer. 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.
The key observation is that this comparison is naturally recursive. Two trees are the same if and only if: (1) their root values match, (2) their left subtrees are the same, and (3) their right subtrees are the same. If any of these three conditions fails, the trees aren't the same.
Key Constraints:
Number of nodes in [0, 100]→ With n up to 100, virtually any approach works. Both recursive and iterative approaches run in O(n) time.-10^4 <= Node.val <= 10^4→ Values can be negative, so we need to compare values directly.0 nodesis valid → Both trees can be empty. Two empty trees are considered the same.
Approach 1: Recursive DFS
Intuition
The most natural way to compare two trees is to walk through them simultaneously, node by node, and check if everything matches at each step.
At any point during our traversal, we're looking at one node from tree p and one node from tree q. There are really only three scenarios:
- Both nodes are null. Great, 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.
That's the entire algorithm. The recursion handles the rest, breaking the problem into smaller and smaller subtrees until we hit null nodes (the base cases). If we make it through every node without finding 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 is clean and correct, but it relies on the call stack. What if we wanted to avoid recursion and compare the trees level by level using our own data structure?
Approach 2: Iterative BFS
Intuition
Instead of letting recursion handle the traversal, we can do it ourselves with a queue. The idea is the same: walk through both trees simultaneously and compare nodes. But instead of using the call stack, we use a queue to process nodes level by level.
We push pairs of nodes (one from each tree) into the queue. For each pair we pull out, we check if they match. If they do, we enqueue their children as new pairs. If at any point a pair doesn't match, we know the trees are different.
The queue ensures we process nodes in the same order from both trees. By enqueuing left-with-left and right-with-right, we maintain the structural correspondence between the trees. If at any point a pair doesn't line up (one null, the other not, or different values), we know the trees differ. This is essentially the same comparison logic as the recursive version, just with an explicit data structure managing the traversal order instead of the call stack.
Algorithm
- Create a queue and add the pair
(p, q)to it. - While the queue is not empty:
a. Dequeue a pair of nodes.
b. If both are null, continue to the next pair.
c. If only one is null, return false.
d. If their values differ, return false.
e. Enqueue the pair (node1.left, node2.left).
f. 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.