Same Tree - Solution & Explanation
Problem Statement
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.
Example 1:
Input: p = [1,2,3], q = [1,2,3] Output: true
Example 2:
Input: p = [1,2], q = [1,null,2] Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2] Output: false
Constraints:
- The number of nodes in both trees is in the range
[0, 100]. -104 <= Node.val <= 104
Approach Overview
Problem Overview: You receive two binary trees and need to determine whether they are exactly the same. Two trees are considered the same if they have identical structure and every corresponding node contains the same value.
The comparison must check both structure and values simultaneously. If any node differs in value, or if one tree has a node where the other has null, the trees are not the same.
Approach 1: Recursive Comparison (DFS) (Time: O(n), Space: O(h))
This approach performs a depth-first traversal of both trees at the same time. Start from the root nodes and compare them. If both nodes are null, that subtree matches. If only one node is null or their values differ, the trees are different. Otherwise recursively compare the left children and then the right children.
The key insight: identical trees must match node-by-node and subtree-by-subtree. Recursion naturally mirrors the structure of a binary tree, making the logic straightforward. Each node is visited once, giving O(n) time complexity where n is the number of nodes. The recursion stack depth equals the tree height, which is O(h) space.
This method is the most common solution in interviews and production code because it is concise and clearly expresses the structure comparison.
Approach 2: Iterative Approach using Stacks (Time: O(n), Space: O(h))
The iterative version replaces recursion with an explicit stack. Push a pair of nodes from both trees onto the stack. Repeatedly pop a pair and compare them. If both are null, continue. If one is null or their values differ, return false. Otherwise push their left children as a pair and their right children as another pair.
This method performs the same traversal pattern as a Depth-First Search. The stack holds pairs of nodes that still need comparison. Like the recursive solution, every node is processed once, giving O(n) time. The stack grows at most to the height of the tree, so space complexity is O(h).
An iterative solution is useful when recursion depth could cause stack overflow or when you want explicit control over traversal order. The logic also mirrors how DFS works internally.
Recommended for interviews: The recursive DFS comparison is usually the expected answer because it directly models the problem and takes only a few lines of code. Interviewers often accept the iterative stack solution as well, especially if you explain how it simulates recursion. Understanding both approaches demonstrates solid knowledge of tree traversal and DFS patterns.
Approach 1: Recursive Comparison
This approach involves recursively checking each node of the trees. You start at the roots and compare their values. If they are the same, you proceed to check their left and right subtrees. If at any point the checks fail (either structure or node values don't match), you conclude that the trees are not identical.
We define a recursive function isSameTree which takes two tree nodes as parameters. It first checks if both nodes are null, returning true if they are. If one of them is null, it returns false. If neither is null, it compares their values and recursively checks their left and right children.
Complexity
The time complexity of this approach is O(N), where N is the total number of nodes in the trees, since each node is visited once. The space complexity is O(H) for the recursion stack, where H is the height of the trees.
Approach 2: Iterative Approach using Stacks
This approach involves using a stack to iteratively check whether two trees are identical. You use a stack to simulate the recursive process, always working on node pairs from both trees. For every processed pair, check for value equality, then push their children into the stack to process afterwards (with left and right children being compared correspondingly).
Here we use a custom stack (assume it's implemented in the included 'stack.h') to iteratively check both trees' nodes in an iterative fashion. Nodes from both trees are pushed onto the corresponding stacks and checked for equality in pairs.
Complexity
The time complexity remains O(N) since each node is processed exactly once. Space complexity could also be up to O(H) for the stack usage, being the tree's height.
Approach 3: DFS
We can use the DFS recursive method to solve this problem.
First, determine whether the root nodes of the two binary trees are the same. If both root nodes are null, then the two binary trees are the same. If only one of the root nodes is null, then the two binary trees are definitely different. If both root nodes are not null, then determine whether their values are the same. If they are not the same, then the two binary trees are definitely different. If they are the same, then determine whether the left subtrees of the two binary trees are the same and whether the right subtrees are the same. The two binary trees are the same only when all the above conditions are met.
The time complexity is O(min(m, n)), and the space complexity is O(min(m, n)). Here, m and n are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of layers of recursive calls, which will not exceed the number of nodes in the smaller binary tree.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Approach 4: BFS
We can also use the BFS iterative method to solve this problem.
First, add the root nodes of the two binary trees to two queues. Each time, take out one node from each of the two queues and perform the following comparison operations. If the values of the two nodes are not the same, then the structures of the two binary trees are definitely different. If the values of the two nodes are the same, then determine whether the child nodes of the two nodes are null. If only the left child node of one node is null, then the structures of the two binary trees are definitely different. If only the right child node of one node is null, then the structures of the two binary trees are definitely different. If the structures of the left and right child nodes are the same, then add the left and right child nodes of the two nodes to the two queues respectively. For the next iteration, take out one node from each of the two queues for comparison. When both queues are empty at the same time, it means that we have compared all the nodes, and the structures of the two binary trees are completely the same.
The time complexity is O(min(m, n)), and the space complexity is O(min(m, n)). Here, m and n are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of elements in the queue, which will not exceed the number of nodes in the smaller binary tree.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Comparison | The time complexity of this approach is O(N), where N is the total number of nodes in the trees, since each node is visited once. The space complexity is O(H) for the recursion stack, where H is the height of the trees. |
| Iterative Approach using Stacks | The time complexity remains O(N) since each node is processed exactly once. Space complexity could also be up to O(H) for the stack usage, being the tree's height. |
| DFS | — |
| BFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Comparison (DFS) | O(n) | O(h) | Most common solution. Clean and concise when recursion depth is safe. |
| Iterative DFS using Stack | O(n) | O(h) | Useful when avoiding recursion or when explicit stack control is preferred. |
Video Solution
Same Tree - Leetcode 100 - Python • NeetCode • 189,151 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Same Tree easy or hard?
How to solve Same Tree in O(n)?
What is the best approach for Same Tree?
Is Same Tree asked at Google/Amazon/Meta?
What data structure is used in Same Tree?
What is the time complexity of Same Tree?
Same Tree Python or Java solution approach?
Ready to solve this problem?
Practice Same Tree with our built-in code editor and test cases.
Practice on FleetCode