Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Name the types of binary trees.
4.2.
Name the order of traversals possible for binary trees and define them.
4.3.
Do binary trees always have sorted values?
5.
Conclusion
Last Updated: Mar 27, 2024

Check if a given binary tree is a subtree of another binary tree or not

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will look at the approach to check whether the given binary tree is a subtree of another binary tree or not. 

Problem Statement

Given: A binary tree S, such that it might be a possible subtree of another binary tree T.

Problem: Check whether the given binary tree is a subtree of another binary tree or not. If the binary tree is a subtree, the function will return a true value and if the binary tree is not a subtree, then the function will return a false value.

Sample Examples

Let us consider the following example trees.

In this example, we can see that the given tree S is a subtree of the tree T. Hence, if we check whether the given binary tree is a subtree of another binary tree or not, the function will return a true value.

Brute Force Approach

In the brute force approach, we can traverse the given trees and mark every node as visited or not and simultaneously compare if the two nodes from each tree are identical or not. If they are identical, we can match the children nodes of that particular node and completely check whether the given binary tree is a subtree of another binary tree or not.

Pseudocode

The pseudocode is as follows:

  1. Start with traversal of the given binary trees.
  2. Iterate over every node from the root node in any order - preferably preorder of both the trees.
  3. Compare the nodes from both trees, if similar then check for the similarity of children nodes. 
  4. If children nodes are also similar, return true value indicating that the given binary tree is a subtree of another binary tree.
  5. If not, return false value.

Implementation in C++

/* Program to check whether the given binary tree is a subtree of another binary tree or not */
#include<bits/stdc++.h>
using namespace std;
 
/* Declare a class for the tree tnode*/
class tnode
{
    public:
    int info;
    tnode* lchild;
    tnode* rchild;
};
 
/* function to check whether trees are identical or not */
bool Identical(tnode * r1, tnode *r2)
{
    if (r1 == NULL && r2 == NULL)
        return true;
 
    if (r1 == NULL || r2 == NULL)
        return false;
 
    /* Check if the info of both root tnode and left and right subtree is same or not */
    return (r1->info == r2->info &&
            Identical(r1->lchild, r2->lchild) &&
            Identical(r1->rchild, r2->rchild) );
}
 
 
/* This function returns true value if S is a subtree of T, else false */
bool isSubtree(tnode *T, tnode *S)
{
    if (S == NULL)
        return true;
 
    if (T == NULL)
        return false;

    if (Identical(T, S))
        return true;
 
    /* Check for left and right subtrees */
    return isSubtree(T->lchild, S) || isSubtree(T->rchild, S);
}
 
 
/* Function to allocate a new tnode with the given info and NULL left and right pointers. */
tnode* newTnode(int info)
{
    tnode* Tnode = new tnode();
    Tnode->info = info;
    Tnode->lchild = NULL;
    Tnode->rchild = NULL;
    return(Tnode);
}
 
/* Driver code*/
int main()
{
    // TREE T
    tnode *T = newTnode(35);
    T->rchild = newTnode(9);
    T->rchild->rchild = newTnode(9);
    T->lchild = newTnode(15);
    T->lchild->lchild     = newTnode(24);
    T->lchild->lchild->rchild = newTnode(36);
    T->lchild->rchild     = newTnode(7);
 
    // TREE S
    tnode *S = newTnode(15);
    S->rchild     = newTnode(7);
    S->lchild     = newTnode(24);
    S->lchild->rchild = newTnode(36);
 
 
    if (isSubtree(T, S))
        cout << "Tree S is subtree of Tree T";
    else
        cout << "Tree S is not a subtree of Tree T";
 
    return 0;
}

 

Implementation in Python

# Program to check whether the given binary tree is a subtree of another binary tree or not
class Tnode:
    # Constructor for creating a new node
    def __init__(self, info):
        self.info = info
        self.lchild = None
        self.rchild = None
 
# Function to check if trees are identical or not
def Identical(r1, r2):
    if r1 is None and r2 is None:
        return True
    if r1 is None or r2 is None:
        return False
 
# Check if the info of both roots and left and right subtrees are also same
    return (r1.info == r2.info and
            Identical(r1.lchild , r2.lchild) and
            Identical(r1.rchild, r2.rchild)
            )
 
# This function returns True if S is a subtree of T, else False
def isSubtree(T, S):
    if S is None:
        return True
 
    if T is None:
        return False
 
    if (Identical(T, S)):
        return True
 
    # Check left and right subtrees
    return isSubtree(T.lchild, S) or isSubtree(T.rchild, S)
 
 
# Main Program
 
#TREE T
T = Tnode(35)
T.rchild = Tnode(9)
T.rchild.rchild  = Tnode(9)
T.lchild = Tnode(15)
T.lchild.lchild = Tnode(24)
T.lchild.lchild.rchild = Tnode(36)
T.lchild.rchild = Tnode(7)
 
# TREE S
S = Tnode(15)
S.rchild = Tnode(7)
S.lchild = Tnode(24)
S.lchild.rchild = Tnode(36)
 
if isSubtree(T, S):
    print ("Tree S is subtree of Tree T")
else :
    print ("Tree S is not a subtree of Tree T")

 

Output: 

Tree S is subtree of Tree T

Complexity Analysis

Time Complexity: In this approach, as we have traversed over each node from both the binary trees, where there are m nodes in tree T and n nodes in tree S, therefore, we have traversed over (mxn) nodes in total and hence, the time complexity is O(mxn). If the number of nodes are the same in both the trees, i.e., n nodes then the time complexity will be O(n2).

Space Complexity: We have utilised the auxiliary space of O(n) in this program.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this approach we will use the order of traversal for binary trees. We will store the values of tree nodes following InOrder in one array and in PostOrder in another array. Now, we can simply compare the values of the arrays and check whether there are any identical subarrays or not. If yes, then the given binary tree is a subtree of another binary tree, otherwise no.

Pseudocode

The pseudocode is as follows:

  1. Store the values of binary tree T in inorder traversal into inT[] and in postorder in postT[] array and the values of binary tree S in inorder traversal in inS[] and in postorder in postS[].
  2. Now, iterate through the inorder arrays and check whether there are identical values or not.
  3. If yes, check with the postorder arrays whether the children values corresponding to the following array indexes are also similar or not and if the complete subtree is similar. 
  4. If yes, then return true value else, return false value.

Implementation in C++

/* Program to check whether the given binary tree is a subtree of another binary tree or not */
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
 
// Structure of a tree node
struct Tnode {
    char keynode;
    struct Tnode *lchild, *rchild;
};
 
// Function to create binary tree node
Tnode* newTnode(char item)
{
    Tnode* temp = new Tnode;
    temp->keynode = item;
    temp->lchild = temp->rchild = NULL;
    return temp;
}
 
// Function to store inorder traversal of tree
void Inorder(Tnode* parentnode, char arr[], int& i)
{
    if (parentnode == NULL) {
        arr[i++] = '$';
        return;
    }
    Inorder(parentnode->lchild, arr, i);
    arr[i++] = parentnode->keynode;
    Inorder(parentnode->rchild, arr, i);
}
 
//Function to store preorder traversal of tree 
void Preorder(Tnode* parentnode, char arr[], int& i)
{
    if (parentnode == NULL) {
        arr[i++] = '$';
        return;
    }
    arr[i++] = parentnode->keynode;
    Preorder(parentnode->lchild, arr, i);
    Preorder(parentnode->rchild, arr, i);
}
 
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(Tnode* T, Tnode* S)
{
    if (S == NULL)
        return true;
    if (T == NULL)
        return false;
 
    // Store Inorder traversals of T and S in inT[0..m-1]
    // and inS[0..n-1] respectively
    int m = 0, n = 0;
    char inT[MAX], inS[MAX];
    Inorder(T, inT, m);
    Inorder(S, inS, n);
    inT[m] = '\0', inS[n] = '\0';
 
    // If inS[] is not a substring of inT[], return false
    if (strstr(inT, inS) == NULL)
        return false;
 
    // Store Preorder traversals of T and S in preT[0..m-1]
    // and preS[0..n-1] respectively
    m = 0, n = 0;
    char preT[MAX], preS[MAX];
    Preorder(T, preT, m);
    Preorder(S, preS, n);
    preT[m] = '\0', preS[n] = '\0';
 
    // If preS[] is not a substring of preT[], return false
    // Else return true
    return (strstr(preT, preS) != NULL);
}
 
// Main Program
int main()
{
    Tnode* T = newTnode('a');
    T->lchild = newTnode('b');
    T->rchild = newTnode('d');
    T->lchild->lchild = newTnode('c');
    T->rchild->rchild = newTnode('e');
 
    Tnode* S = newTnode('a');
    S->lchild = newTnode('b');
    S->lchild->lchild = newTnode('c');
    S->rchild = newTnode('d');
 
    if (isSubtree(T, S))
        cout << "Tree S is subtree of Tree T";
    else
        cout << "Tree S is not subtree of Tree T";
 
    return 0;
}

 

Implementation in Python

#Check if the given binary tree is a subtree of another binary tree or not
MAX = 100
 
# class for a tree node
class Tnode:
    def __init__(self):
        self.keynode = ' '
        self.lchild = None
        self.rchild = None
 
# Create binary tree node
def newTnode(item):
    temp = Tnode()
    temp.keynode = item
    return temp
 
# Function to store inorder traversal of tree
def Inorder(parentnode, i):
    if (parentnode == None):
        return '$'
    res = Inorder(parentnode.lchild, i)
    res += parentnode.keynode
    res += Inorder(parentnode.rchild, i)
    return res
 
# Function to store preorder traversal of tree
def Preorder(parentnode, i):
    if (parentnode == None):
        return '$'
    res = parentnode.keynode
    res += Preorder(parentnode.lchild, i)
    res += Preorder(parentnode.rchild, i)
    return res
 
# This function returns true if S is a subtree of T, otherwise false
def isSubtree(T, S):
    if (S == None):
        return True
    if (T == None):
        return False
 
    # Store Inorder traversals of T and S in inT[0..m-1]
    # and inS[0..n-1] respectively
    m = 0
    n = 0
    inT = Inorder(T, m)
    inS = Inorder(S, n)
 
    # If inS[] is not a substring of inT[], return false
    res = True
    if inS in inT:
        res = True
    else:
        res = False
    if(res == False):
        return res
 
    # Store Preorder traversals of T and S in preT[0..m-1]
    # and preS[0..n-1] respectively
    m = 0
    n = 0
    preT = Preorder(T, m)
    preS = Preorder(S, n)
 
    # If preS[] is not a substring of preT[], return false
    # Else return true
    if preS in preT:
        return True
    else:
        return False
 
# Main program
T = newTnode('a')
T.lchild = newTnode('b')
T.rchild = newTnode('d')
T.lchild.lchild = newTnode('c')
T.rchild.rchild = newTnode('e')
 
S = newTnode('a')
S.lchild = newTnode('b')
S.lchild.lchild = newTnode('c')
S.rchild = newTnode('d')
 
if (isSubtree(T, S)):
    print("Tree S is subtree of Tree T")
else:
    print("Tree S is not a subtree of Tree T")

 

Output: 

Tree S is not a subtree of Tree T

Complexity Analysis

Time Complexity: In the optimized approach, the time complexity is reduced to O(n) because inorder and preorder traversals of the binary tree to store the values of the nodes in the arrays take O(n) time.

Space Complexity: The space complexity is O(n) because the auxiliary space used is O(n).

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

Name the types of binary trees.

The six types of binary trees are full, complete, perfect, degenerate, skewed, balanced.

Name the order of traversals possible for binary trees and define them.

Inorder traversal stores the values in the order of left child, root, right child. Preorder stores in the form of root, left child, right child and Postorder stores in the form of left child, right child and root.

Do binary trees always have sorted values?

No, not all binary trees have values in a sorted order however, binary search trees contain values such that the value of the key in left subtree is less than the parent node and the value of the key in right subtree is greater than the parent node, which may be considered as a sorted order.

Conclusion

This article discussed the approach to checking whether the given binary tree is a subtree of another binary tree or not. We have also implemented the pseudocode for checking whether the given binary tree is a subtree of another binary tree in Python and C++.

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Check if all leaves are at the same level
Next article
Check if a Binary Tree has Duplicate Values
Live masterclass