Check If Two Binary Trees Are Identical

93k
0

Given the roots of two binary trees, p and q, determine whether the two trees are identical.

Two binary trees are identical only if:

  • Their structure is exactly the same.

  • Nodes at corresponding positions contain the same values.

If both trees are empty, they are considered identical. If only one tree is empty, they are not identical.

Example 1

Input: p = [1, 2, 3], q = [1, 2, 3]

Output: true

Explanation: Both trees have the same structure, and every pair of corresponding nodes contains the same value. Therefore, the trees are identical.

Example 2

Input: p = [1, 2], q = [1, null, 2]

Output: false

Explanation: Both trees contain the values 1 and 2, but their structures are different. In p, node 2 is the left child of 1, while in q, node 2 is the right child of 1. Therefore, the trees are not identical.

Approach 1

Two trees are identical only when the nodes at every corresponding position match in both existence and value.

Recursion fits naturally because after comparing the current pair of nodes, the same condition must hold for their left subtrees and their right subtrees.

If both current nodes are null, that position matches. If only one is null, the structure differs. Otherwise, their values must match before checking the corresponding children.

Algorithm

  • If both p and q are null, return true because both subtrees are empty.

  • If exactly one of them is null, return false because their structures differ.

  • Compare p.val and q.val; return false immediately if the values are different.

  • Recursively compare p.left with q.left to verify the left subtrees.

  • Recursively compare p.right with q.right to verify the right subtrees.

  • Return true only if both recursive comparisons are true.

Dry Run

Same Tree Appraoch 1 Dry Run.png

Same Tree Appraoch 1 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Compares corresponding nodes
// of both trees recursively.
bool isSameTree(TreeNode* p, TreeNode* q) {
// Both trees are empty
// at this position.
if (p == nullptr && q == nullptr) {
return true;
}
// Only one node exists,
// so the structures differ.
if (p == nullptr || q == nullptr) {
return false;
}
// Different values make
// the trees non-identical.
if (p->val != q->val) {
return false;
}
// Both corresponding subtrees
// must also be identical.
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
int main() {
TreeNode* p = new TreeNode(1);
p->left = new TreeNode(2);
p->right = new TreeNode(3);
TreeNode* q = new TreeNode(1);
q->left = new TreeNode(2);
q->right = new TreeNode(3);
Solution solution;
cout << (
solution.isSameTree(p, q)
? "true"
: "false"
) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in either tree in the worst case. Every corresponding node position is checked at most once.

Space Complexity: O(H), where H is the maximum height of the two trees, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 2

The recursive solution compares corresponding positions in both trees. The same comparison can be performed iteratively by storing pairs of corresponding nodes in a queue.

For every pair, first verify that their structure matches and then compare their values. If the pair is valid, their left children are paired together and their right children are paired together.

Any mismatch can return false immediately.

Algorithm

  • Push the initial pair (p, q) into a queue because comparison begins at the roots.

  • Remove one pair at a time from the queue.

  • If both nodes are null, continue because that position matches; if exactly one is null, return false.

  • If both nodes exist but their values differ, return false.

  • Push their left children as one pair and their right children as another pair so corresponding positions remain aligned.

  • If every pair is processed without a mismatch, return true.

Dry Run

Same Tree Appraoch 2 Dry Run.png

Same Tree Appraoch 2 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Compares corresponding nodes
// using breadth-first traversal.
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<pair<TreeNode*, TreeNode*>> qNodes;
// Start comparison from
// the two root nodes.
qNodes.push({p, q});
// Process one corresponding
// node pair at a time.
while (!qNodes.empty()) {
auto [nodeP, nodeQ] = qNodes.front();
qNodes.pop();
// Both positions are empty,
// so this pair matches.
if (nodeP == nullptr && nodeQ == nullptr) {
continue;
}
// Only one node exists,
// so the structures differ.
if (nodeP == nullptr || nodeQ == nullptr) {
return false;
}
// Corresponding nodes must
// contain the same value.
if (nodeP->val != nodeQ->val) {
return false;
}
// Keep corresponding children
// paired for later comparison.
qNodes.push({
nodeP->left,
nodeQ->left
});
qNodes.push({
nodeP->right,
nodeQ->right
});
}
return true;
}
};
int main() {
TreeNode* p = new TreeNode(1);
p->left = new TreeNode(2);
p->right = new TreeNode(3);
TreeNode* q = new TreeNode(1);
q->left = new TreeNode(2);
q->right = new TreeNode(3);
Solution solution;
cout << (
solution.isSameTree(p, q)
? "true"
: "false"
) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in either tree in the worst case. Every corresponding node pair is processed at most once.

Space Complexity: O(W), where W is the maximum width of the two trees. The queue may hold up to O(W) corresponding node pairs at the same time, which can become O(N) in the worst case.

Approach 3

Recursive DFS does not require level-order processing; it only needs corresponding positions from the two trees to remain paired.

The recursion stack can therefore be replaced with an explicit stack containing (nodeFromP, nodeFromQ) pairs. Each pair undergoes the same structural and value checks as in the recursive solution.

This avoids recursion while preserving the depth-first comparison order.

Algorithm

  • Push (p, q) into a stack to begin comparison from the roots.

  • Pop one pair at a time while the stack is not empty.

  • If both nodes are null, continue; if exactly one is null, return false.

  • If both nodes exist but their values differ, return false.

  • Push the corresponding right children first and the corresponding left children afterward, so the left pair is processed next and the traversal follows depth-first order.

  • If the stack becomes empty without finding any mismatch, return true.

Dry Run

Same Tree Appraoch 3 Dry Run.png

Same Tree Appraoch 3 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Compares corresponding nodes
// using an explicit DFS stack.
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<pair<TreeNode*, TreeNode*>> st;
// Begin comparison from
// the two root nodes.
st.push({p, q});
// Process one corresponding
// node pair at a time.
while (!st.empty()) {
auto [nodeP, nodeQ] = st.top();
st.pop();
// Both positions are empty,
// so this pair matches.
if (nodeP == nullptr && nodeQ == nullptr) {
continue;
}
// Only one node exists,
// so the structures differ.
if (nodeP == nullptr || nodeQ == nullptr) {
return false;
}
// Corresponding nodes must
// contain the same value.
if (nodeP->val != nodeQ->val) {
return false;
}
// Push right first so
// the left pair is checked next.
st.push({
nodeP->right,
nodeQ->right
});
st.push({
nodeP->left,
nodeQ->left
});
}
return true;
}
};
int main() {
TreeNode* p = new TreeNode(1);
p->left = new TreeNode(2);
p->right = new TreeNode(3);
TreeNode* q = new TreeNode(1);
q->left = new TreeNode(2);
q->right = new TreeNode(3);
Solution solution;
cout << (
solution.isSameTree(p, q)
? "true"
: "false"
) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in either tree in the worst case. Every corresponding node pair is processed at most once.

Space Complexity: O(H), where H is the maximum height of the two trees. The explicit DFS stack can grow to O(H), which becomes O(N) for a skewed tree.

FAQs

Q1. Are two empty binary trees considered identical?

Yes. If both roots are null, both trees have the same empty structure, so they are identical.

Q2. Why must both structure and values be compared?

Equal values alone are not enough. A node may appear as a left child in one tree and a right child in the other, which means the structures are different.

Q3. Why can the algorithm return immediately after finding one mismatch?

Identical trees require every corresponding position to match. Therefore, a single structural or value mismatch is enough to prove that the trees are different.

Q4. Can tree serialization be used instead?

Yes. Both trees can be serialized with explicit null markers and the resulting representations can be compared. Direct node-by-node comparison is usually simpler and can stop as soon as a mismatch is found.

Q5. Which approach is preferable in interviews?

Recursive DFS is usually the simplest first solution because it directly mirrors the recursive definition of identical trees. BFS or iterative DFS are useful alternatives when recursion depth is a concern.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot , determine whether subRoot appears as a subtree of root . A subtree must match an entire tree section starting from some node in root , includ...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

Given the root of a complete binary tree , determine the total number of nodes present in the tree. In a complete binary tree: Every level except possibly the last is completely filled. Nodes in th...

54.2k
Comments0