C++ Program to Check if two trees are Identical
In this article, we will learn how to implement a program to check whether the given two trees are identical or not in C++. Two trees are said to identical when they have the same data and the arrangement of the data is also the same.
Check Whether Two Trees are Identical in C++
1. Firstly, check base condition if both trees are NULL then return 1.
2. Now check if both trees are not equal NULL then
- return true if root1->data == root2->data && identicalTree(root1->left, root2->left) && identicalTree(root1->right, root2->right)
3. For all the remaining cases return 0.
#include <bits/stdc++.h> using namespace std; struct Node{ int data; Node* left; Node* right; }; // function to create a new node Node* newNode(int data){ Node* node = new Node(); node->data = data; node->left = NULL; node->right = NULL; return node; } // function return true if the given trees are identical else returns false int identicalTree(Node* root1, Node* root2){ if (root1 == NULL && root2 == NULL) return 1; if (root1 != NULL && root2 != NULL){ return (root1->data == root2->data && identicalTree(root1->left, root2->left) && identicalTree(root1->right, root2->right)); } return 0; } int main(){ // tree 1 Node* root1 = newNode(1); root1->right = newNode(2); root1->left = newNode(3); root1->right->left = newNode(4); root1->right->right = newNode(5); root1->left->right = newNode(6); root1->left->right = newNode(7); // tree 2 Node* root2 = newNode(1); root2->right = newNode(2); root2->left = newNode(3); root2->right->left = newNode(4); root2->right->right = newNode(5); root2->left->right = newNode(6); root2->left->right = newNode(7); if(identicalTree(root1, root2)) cout<<"Identical Trees"<<endl; else cout<<"Non identical trees"<<endl; }
Output
Identical Trees
Also, read
Leave a Reply