Approach Summary
Recursively verify whether two binary trees are structurally identical with equal node values. If both are null return true; if one is null or values differ, return false.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Synchronized Recursive DFS (Optimal) | O(n) | O(h) call stack | Traverse both trees recursively, verifying structural and value equality at every node. |
| 2 Approach 2: Iterative BFS using Queue | O(n) | O(w) queue memory | Enqueue corresponding node pairs from both trees to compare level by level without recursion. |
Step 1: Baseline
Approach 1: Synchronized Recursive DFS (Optimal)
Time: O(n)
Space: O(h) call stack
At each recursive step: if both nodes are null, this branch matches (return true). If only one node is null, or if their values differ, return false. Finally, return the conjunction of recursively checking both left subtrees and right subtrees. This elegant formulation visits each node once.
Approach 1: Synchronized Recursive DFS (Optimal) Implementation
Approach 1: Synchronized Recursive DFS (Optimal)
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null || p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL || p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};def is_same_tree(p, q) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
} Step 2: Most Optimized
Approach 2: Iterative BFS using Queue
Time: O(n)
Space: O(w) queue memory
Push root pairs (p, q) into a queue. While the queue is not empty, dequeue a pair (node1, node2). If both are null, continue. If one is null or values differ, return false. Otherwise, enqueue both left children (node1.left, node2.left) and both right children (node1.right, node2.right). If the loop finishes, the trees are identical. This avoids stack overflow on deep trees.
Approach 2: Iterative BFS using Queue Implementation
Approach 2: Iterative BFS using Queue
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
TreeNode n1 = queue.poll();
TreeNode n2 = queue.poll();
if (n1 == null && n2 == null) continue;
if (n1 == null || n2 == null || n1.val != n2.val) return false;
queue.offer(n1.left);
queue.offer(n2.left);
queue.offer(n1.right);
queue.offer(n2.right);
}
return true;
}
}class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<pair<TreeNode*, TreeNode*>> qNodes;
qNodes.push({p, q});
while (!qNodes.empty()) {
auto [n1, n2] = qNodes.front(); qNodes.pop();
if (!n1 && !n2) continue;
if (!n1 || !n2 || n1->val != n2->val) return false;
qNodes.push({n1->left, n2->left});
qNodes.push({n1->right, n2->right});
}
return true;
}
};from collections import deque
def is_same_tree(p, q) -> bool:
queue = deque([(p, q)])
while queue:
n1, n2 = queue.popleft()
if not n1 and not n2:
continue
if not n1 or not n2 or n1.val != n2.val:
return False
queue.append((n1.left, n2.left))
queue.append((n1.right, n2.right))
return Truefunction isSameTree(p, q) {
const queue = [[p, q]];
while (queue.length > 0) {
const [n1, n2] = queue.shift();
if (!n1 && !n2) continue;
if (!n1 || !n2 || n1.val !== n2.val) return false;
queue.push([n1.left, n2.left]);
queue.push([n1.right, n2.right]);
}
return true;
}Edge Cases to Watch
- Both trees are null (returns true)
- One tree is null and the other is not (returns false)
- Trees have identical values but mirror/different structures
- Large trees with values differing only at the deepest leaf
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Check if two trees have identical structure and values
- Simultaneous synchronized tree recursion
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree Depth-First Search Breadth-First Search Binary Tree
Frequently Asked Questions
What is the optimal time and space complexity for Same Tree?
The optimal solution for Same Tree achieves O(n) runtime complexity and requires O(h) auxiliary space. Every node in both trees is visited at most once, taking O(n) time where n is the minimum number of nodes in either tree. Recursion depth is bounded by tree height h, requiring O(h) call stack memory (O(log n) for balanced trees, O(n) for skewed trees).
How do I identify that Same Tree requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Check if two trees have identical structure and values; Simultaneous synchronized tree recursion. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Same Tree?
Essential edge cases to verify include: Both trees are null (returns true); One tree is null and the other is not (returns false); Trees have identical values but mirror/different structures; Large trees with values differing only at the deepest leaf. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Same Tree?
Same Tree is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Microsoft.