Watch 10 video solutions for Same Tree, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by Inside code has 224,572 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 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 | 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. |