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:
[0, 100].-104 <= Node.val <= 104Problem Overview: Given two binary trees, determine whether they are structurally identical and contain the same values at every corresponding node. Two trees are considered the same only if both the structure and the node values match exactly.
Approach 1: Recursive Comparison (DFS) (Time: O(n), Space: O(h))
This approach performs a depth-first traversal of both trees simultaneously using recursion. At each step, compare the current nodes: if both are null, the structures match at that branch; if only one is null or their values differ, the trees are not identical. When values match, recursively compare the left children and then the right children. The key insight is that identical trees must have identical subtrees at every level, so a mismatch anywhere immediately returns false. Time complexity is O(n) because every node is visited once, where n is the number of nodes. Space complexity is O(h) due to the recursion stack, where h is the tree height. This approach naturally fits problems involving Depth-First Search on a Binary Tree.
Approach 2: Iterative Approach using Stacks (Time: O(n), Space: O(n))
The iterative version simulates DFS using an explicit stack instead of recursion. Push the root nodes of both trees as a pair. Each iteration pops a pair of nodes and checks three conditions: both are null, one is null, or their values differ. If values match, push their children in corresponding order (left-left and right-right) onto the stack. This keeps comparisons aligned between the two trees. The algorithm still visits each node once, giving O(n) time complexity. Space complexity can reach O(n) in the worst case when the tree is skewed or many nodes are stored in the stack. Iterative traversal avoids recursion limits and provides explicit control over the traversal order, a common pattern in Tree problems.
Recommended for interviews: Recursive DFS is the expected solution. The code is concise and mirrors the recursive structure of trees, making correctness easy to reason about. Interviewers often look for the base cases: both nodes null, one null, and value mismatch. After that, combining the results of left and right subtree comparisons shows strong understanding of tree recursion. The iterative stack approach demonstrates the same logic without recursion and is useful when discussing stack simulation or when recursion depth could be large.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Comparison (DFS) | O(n) | O(h) | Best general solution for binary tree comparison; concise and commonly expected in interviews |
| Iterative DFS using Stack | O(n) | O(n) | Useful when avoiding recursion limits or when demonstrating explicit stack-based traversal |
How to solve (almost) any binary tree coding problem • Inside code • 224,572 views views
Watch 9 more video solutions →Practice Same Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor