Given two binary trees, determine if they are structurally identical and have the same node values at corresponding positions.
Table of Contents
Sample Input:
Tree 1:
1
/ \
2 3
Tree 2:
1
/ \
2 3
Expected Output:
true
In this example, both binary trees are identical in structure, and they have the same node values at corresponding positions. The function should return true.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node in both trees once to compare them. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the taller tree.
C++ solution:
#include <iostream>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
bool isSameTree(TreeNode* p, TreeNode* q) {
// Base case: if both nodes are null, they are equal
if (p == nullptr && q == nullptr) {
return true;
}
// If one of the nodes is null and the other is not, they are not equal
if (p == nullptr || q == nullptr) {
return false;
}
// Check if the current nodes have the same value
if (p->val != q->val) {
return false;
}
// Recursively check the left and right subtrees
bool leftSubtreeSame = isSameTree(p->left, q->left);
bool rightSubtreeSame = isSameTree(p->right, q->right);
// Return true only if both subtrees are also the same
return leftSubtreeSame && rightSubtreeSame;
}
int main() {
// Construct the binary trees for the sample input
TreeNode* tree1 = new TreeNode(1);
tree1->left = new TreeNode(2);
tree1->right = new TreeNode(3);
TreeNode* tree2 = new TreeNode(1);
tree2->left = new TreeNode(2);
tree2->right = new TreeNode(3);
// Check if the two binary trees are the same
if (isSameTree(tree1, tree2)) {
std::cout << "The two binary trees are the same.\n";
} else {
std::cout << "The two binary trees are not the same.\n";
}
return 0;
}
The isSameTree function recursively checks if two binary trees are the same. It starts from the root nodes of both trees and compares their values. If the current nodes have the same value, the function recursively checks their left and right subtrees. It returns true only if both subtrees are also the same.
In the given example, the function will correctly determine that the two binary trees are the same, and the output will be true.
As mentioned earlier, the time complexity is O(n) as we need to visit each node in both trees once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the taller tree.