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 <= 104The goal of #100 Same Tree is to determine whether two binary trees are structurally identical and contain the same values. A common way to think about this problem is to compare corresponding nodes from both trees simultaneously.
The most intuitive method uses Depth-First Search (DFS) with recursion. At each step, check three conditions: both nodes are null, only one node is null, or both nodes exist but their values differ. If the values match, recursively compare their left children and right children. This mirrors the natural structure of binary trees and keeps the logic clean.
Another valid approach is Breadth-First Search (BFS) using a queue. Push pairs of nodes from the two trees and compare them level by level. If at any step the structure or values differ, the trees are not the same.
Both strategies visit each node once, making them efficient for interview scenarios involving tree comparison.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS (Recursive) | O(n) | O(h) |
| BFS (Queue) | O(n) | O(n) |
Inside code
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.
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.
1#include <iostream>
2using namespace std;
3struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
4bool isSameTree(TreeNode* p, TreeNode* q) {
5 if (!p && !q) return true;
6 if (!p || !q) return false;
7 return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
8}The solution in C++ is similar to C. We define a struct for the TreeNode and use a recursive function isSameTree that checks if two trees are identical by comparing the root values and recursively checking the left and right subtrees.
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).
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.
1using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> stackP, stackQ;
stackP.push(p);
stackQ.push(q);
while (!stackP.empty() && !stackQ.empty()) {
TreeNode* nodeP = stackP.top(); stackP.pop();
TreeNode* nodeQ = stackQ.top(); stackQ.pop();
if (!nodeP && !nodeQ) continue;
if (!nodeP || !nodeQ || nodeP->val != nodeQ->val) return false;
stackP.push(nodeP->right); stackP.push(nodeP->left);
stackQ.push(nodeQ->right); stackQ.push(nodeQ->left);
}
return stackP.empty() && stackQ.empty();
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Same Tree is a common foundational tree problem often asked in coding interviews, including FAANG-style interviews. It tests understanding of binary tree traversal, recursion, and structural comparison.
Yes, the problem can be solved iteratively using Breadth-First Search with a queue. By pushing pairs of nodes from both trees into the queue and comparing them step by step, you can verify if the structures and values match.
The optimal approach is typically a Depth-First Search (DFS) using recursion. It compares corresponding nodes from both trees and recursively checks their left and right subtrees. This method is simple, readable, and runs in linear time.
Binary trees themselves are the main data structure involved. For traversal, recursion (call stack) is commonly used, while an iterative solution may use a queue to perform Breadth-First Search and compare node pairs level by level.
The C++ solution uses a stack from the standard library to iteratively compare tree nodes. The approach mimics tree traversal using stack operations for both trees in tandem.