C C++ JAVA PYTHON SQL HTML CSS DSA Robotics AWS CODING INTERVIEW PREPARATION

Made with  & Code

# Check for subtree in a Binary Tree

Written By -

## 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;

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);
}

bool isSubTree(Node* root, Node* sub) {
if(sub == NULL) return 1;
if(sub && !root) return 0;

if(root->data == sub->data){
bool res =  isIdentical(root, sub);
if(res) return true;
}

return isSubTree(root->left, sub) ||  isSubTree(root->right, sub);
}

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<<isSubTree(root, root);

return 0;
}``````

TC- O(MN) // where M and N are the number of nodes in given tree

Related Posts:

Online Compilers