Recent Posts

Check for subtree in a Binary Tree

Written by

studymite

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



}


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


if(root-&gt;data == sub-&gt;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

Check for subtree in a Binary Tree