Recent Posts

Check for identical binary trees

Written by

studymite

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 &amp;&amp; !root2) || (!root1 &amp;&amp; root2)) return false;

if(root1-&gt;data != root2-&gt;data) return false;

return isIdentical(root1-&gt;left, root2-&gt;left) &amp;&amp; isIdentical(root1-&gt;right, root2-&gt;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)

Check for identical binary trees