Introduction
In this blog we will discuss the problem, i.e., " Check if Two Binary Trees are Identical,". It is highly asked in product-based companies. We'll go over all the steps of the solution.
Let's get started with the problem statement without further ado.
Prerequisites
Knowledge of trees and related terminologies such as recursion, trees, and the main traversals inorder, preorder, postorder are common prerequisites for every tree problem. It is not advisable to proceed to Check if Two Binary Trees are Identical in trees without mastering these fundamental methods and data structures.
Nonetheless, we'll try to go through every detail needed to Check if Two Binary Trees are Identical.
Problem Statement
Write an efficient algorithm to Check if Two Binary Trees are Identical. If two binary trees contain identical structures and data, they are said to be identical.
To determine whether two trees are identical, we must traverse both trees simultaneously and compare the data and children of the trees.
Sample Example
Input:
Output: True
Explanation: The structure and contents of both binary trees are identical.
Approach
To determine whether two trees are the same, we must walk both trees simultaneously and compare their data and children.
Pseudocode
Check if Two Binary Trees are Identical (Binary Tree 1, Binary Tree 2)
1. If both binary trees are empty, then return TRUE.
2. Else If both binary trees are non-empty
(a) Check data of the root nodes (root node root Binary Tree 1->data == root node of Binary Tree 2->data)
(b) Check left subtrees recursively, i.e., Check if Two Binary Trees are Identical(
Binary Tree 1->left_subtree, Binary Tree 2->left_subtree)
(c) Check right subtrees recursively, i.e., Check if Two Binary Trees are Identical(
Binary Tree 1->right_subtree, Binary Tree 2->right_subtree)
(d) If a,b and c are true then return TRUE.
3 Else return FALSE (one is empty, and the other is not)
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node * left;
node * right;
};
node * newNode(int data) {
node * Node = new node();
Node -> data = data;
Node -> left = NULL;
Node -> right = NULL;
return (Node);
}
/* Function to Check if Two Binary Trees are Identical */
bool Check_if_Two_Binary_Trees_are_Identical(node * root1, node * root2) {
/* if both binary trees are empty then return TRUE. */
if (root1 == NULL && root2 == NULL)
return true;
if (root1 != NULL && root2 != NULL) {
/*Check data of the root nodes */
bool a = root1 -> data == root2 -> data;
/*Check left subtrees recursively*/
bool b = Check_if_Two_Binary_Trees_are_Identical(root1 -> left, root2 -> left);
/*Check right subtrees recursively*/
bool c = Check_if_Two_Binary_Trees_are_Identical(root1 -> right, root2 -> right);
return a && b && c;
}
return false;
}
/* Driver code*/
int main() {
cout << "Check if Two Binary Trees are Identical : ";
/*Binary tree 1*/
node * root1 = newNode(6);
root1 -> left = newNode(5);
root1 -> right = newNode(9);
root1 -> left -> left = newNode(12);
root1 -> left -> right = newNode(3);
root1 -> right -> left = newNode(7);
root1 -> right -> right = newNode(6);
/*Binary tree 2*/
node * root2 = newNode(6);
root2 -> left = newNode(5);
root2 -> right = newNode(9);
root2 -> left -> left = newNode(12);
root2 -> left -> right = newNode(3);
root2 -> right -> left = newNode(7);
root2 -> right -> right = newNode(6);
if (Check_if_Two_Binary_Trees_are_Identical(root1, root2))
cout << "Both trees are identical.";
else
cout << "Trees are not identical.";
return 0;
}
Output:
Check if Two Binary Trees are Identical : Both trees are identical.
Complexity Analysis
Time complexity: O(n)
According to the tree with a lesser number of nodes. Let the number of nodes in two trees be m and n; then complexity will be O(m) where m <n.
Space complexity: O(1)
No extra space is used.
Check out this problem - Duplicate Subtree In Binary Tree
7+ registered 
