TutorialStudyMite
Check for identical binary trees
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
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;
}
int main() {
/*
1
/
2 3
/ \ /
4 5 6 7
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);
}TC – O(N)
Finished reading?