TutorialStudyMite
Check for subtree in a Binary Tree
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
Problem
Given two binary trees with their head nodes root and sub. We need to find that sub is the subtree of root.
Approach
In this problem, we will need to check identical trees.
- If sub is NULL then the tree is a subtree of root.
- If the subtree is not NULL and the root is NULL then it's not the subtree.
- Then we'll check the data of both the nodes and if the data is equal then we will check if the tree is identical or not.
- The above steps recursively perform on 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;
}
bool isSubTree(Node* root, Node* sub) {
if(sub == NULL) return 1;
if(sub && !root) return 0;
return isSubTree(root->left, sub) || isSubTree(root->right, sub);
}
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<<isSubTree(root, root);
}TC- O(MN) // where M and N are the number of nodes in given tree
Finished reading?