& Code
Problem
We need to check that the given trees are identical or not.
Approach
We will check for each node in both the trees.
There will be three cases:
- If the root of both trees is NULL this means trees are identical.
- If one node is NULL and the other is not, this means trees are not identical.
- If both node’s data is not equal then trees are not identical.
- Now we will recursively traverse all the nodes and follow the above steps for every node.
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
bool isIdentical(Node *root1, Node *root2){
if(root1 == NULL && root2 == NULL) return true;
if((root1 && !root2) || (!root1 && root2)) return false;
if(root1->data != root2->data) return false;
return isIdentical(root1->left, root2->left) && isIdentical(root1->right, root2->right);
}
int main() {
/*
1
/ \
2 3
/ \ / \
4 5 6 7
*/
struct Node* root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
cout<<isIdentical(root, root);
return 0;
}TC – O(N)
Report Error/ Suggestion