In this chapter, we shall see if 2 trees are identical.
Problem statement:
You are given root node of 2 binary trees, you need to check if 2 trees are identical.
Example:
Consider the below image
The first set are identical; the second set are not identical.
From the image we can derive below true cases:
- If both nodes are null, then return true
- If the right node value of tree 1 is equal to the right node value of tree 2, return true.
- If the Left node value of tree 1 is equal to the Left node value of tree 2, return true.
From the image we can derive below false cases:
- If a node from tree 1 has value, and node from tree 2 is null, then return false.
- If both the tree nodes have a value, but they are different, then return false.
Solution in C++
#include <iostream> #include <stack> #include <map> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int check_is_identical(Node* root1, Node* root2) { if (root1 == NULL && root2 == NULL) return 1; else if (root1 != NULL && root2 == NULL) return 0; else if (root1 == NULL && root2 != NULL) return 0; else { if (root1->data == root2->data && check_is_identical(root1->left, root2->left) && check_is_identical(root1->right, root2->right)) return 1; else return 0; } } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); Node* root_1 = nullptr; /* Binary tree: 16 / \ / \ 25 10 / \ / \ / \ / \ 30 18 15 7 */ root_1 = new Node(16); root_1->left = new Node(25); root_1->right = new Node(10); root_1->left->left = new Node(30); root_1->left->right = new Node(18); root_1->right->left = new Node(15); root_1->right->right = new Node(7); if(check_is_identical(root, root_1)) { cout<<"Both of them are identical"<<endl; } else { cout<<"Both of them are not identical"<<endl; } return 0; }
Output:
Both of them are not identical