Data Modelling & AI Data Structure & Algorithm

Check if a Binary Tree is subtree of another binary tree | Set 1

20 June 2025

0

Given two binary trees, check if the first tree is a subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Examples:

Input:

Tree S
10
/ \
4 6
\
30

Tree T
26
/ \
10 3
/ \ \
4 6 3
\
30
Output: S is subtree of tree T

Approach:

The idea is to check at every node for the subtree.

Follow the steps below to solve the problem:

Traverse the tree T in preorder fashion
For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
To check the subtree is identical or not traverse on the tree S and T simultaneously
If a visited node is not equal then return false else continue traversing the whole tree S is traversed

Below is the implementation of above approach:

C++

// C++ program to check if binary tree
// is subtree of another binary tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data,
left child and right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
/* A utility function to check
whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(node* root1, node* root2)
{
    /* base cases */
    if (root1 == NULL && root2 == NULL)
        return true;
 
    if (root1 == NULL || root2 == NULL)
        return false;
 
    /* Check if the data of both roots is
    same and data of left and right
    subtrees are also same */
    return (root1->data == root2->data
            && areIdentical(root1->left, root2->left)
            && areIdentical(root1->right, root2->right));
}
 
/* This function returns true if S
is a subtree of T, otherwise false */
bool isSubtree(node* T, node* S)
{
    /* base cases */
    if (S == NULL)
        return true;
 
    if (T == NULL)
        return false;
 
    /* Check the tree with root as current node */
    if (areIdentical(T, S))
        return true;
 
    /* If the tree with root as current
    node doesn't match then try left
    and right subtrees one by one */
    return isSubtree(T->left, S) || isSubtree(T->right, S);
}
 
/* Helper function that allocates
a new node with the given data
and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return (Node);
}
 
/* Driver code*/
int main()
{
    // TREE 1
    /* Construct the following tree
            26
            / \
        10 3
        / \ \
    4 6 3
    \
        30
    */
    node* T = newNode(26);
    T->right = newNode(3);
    T->right->right = newNode(3);
    T->left = newNode(10);
    T->left->left = newNode(4);
    T->left->left->right = newNode(30);
    T->left->right = newNode(6);
 
    // TREE 2
    /* Construct the following tree
        10
        / \
    4 6
    \
        30
    */
    node* S = newNode(10);
    S->right = newNode(6);
    S->left = newNode(4);
    S->left->right = newNode(30);
 
    if (isSubtree(T, S))
        cout << "Tree 2 is subtree of Tree 1";
    else
        cout << "Tree 2 is not a subtree of Tree 1";
 
    return 0;
}
 
// This code is contributed by rathbhupendra

C

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, left child and right child
 */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* A utility function to check whether trees with roots as
   root1 and root2 are identical or not */
bool areIdentical(struct node* root1, struct node* root2)
{
    /* base cases */
    if (root1 == NULL && root2 == NULL)
        return true;
 
    if (root1 == NULL || root2 == NULL)
        return false;
 
    /* Check if the data of both roots is same and data of
       left and right subtrees are also same */
    return (root1->data == root2->data
            && areIdentical(root1->left, root2->left)
            && areIdentical(root1->right, root2->right));
}
 
/* This function returns true if S is a subtree of T,
 * otherwise false */
bool isSubtree(struct node* T, struct node* S)
{
    /* base cases */
    if (S == NULL)
        return true;
 
    if (T == NULL)
        return false;
 
    /* Check the tree with root as current node */
    if (areIdentical(T, S))
        return true;
 
    /* If the tree with root as current node doesn't match
       then try left and right subtrees one by one */
    return isSubtree(T->left, S) || isSubtree(T->right, S);
}
 
/* Helper function that allocates a new node with the given
   data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
 
/* Driver program to test above function */
int main()
{
    // TREE 1
    /* Construct the following tree
              26
            /   \
          10     3
        /    \     \
      4      6      3
       \
        30
    */
    struct node* T = newNode(26);
    T->right = newNode(3);
    T->right->right = newNode(3);
    T->left = newNode(10);
    T->left->left = newNode(4);
    T->left->left->right = newNode(30);
    T->left->right = newNode(6);
 
    // TREE 2
    /* Construct the following tree
          10
        /    \
      4      6
       \
        30
    */
    struct node* S = newNode(10);
    S->right = newNode(6);
    S->left = newNode(4);
    S->left->right = newNode(30);
 
    if (isSubtree(T, S))
        printf("Tree 2 is subtree of Tree 1");
    else
        printf("Tree 2 is not a subtree of Tree 1");
 
    getchar();
    return 0;
}

Java

// Java program to check if binary tree is subtree of
// another binary tree
 
// A binary tree node
class Node {
    int data;
    Node left, right, nextRight;
 
    Node(int item)
    {
        data = item;
        left = right = nextRight = null;
    }
}
 
class BinaryTree {
    Node root1, root2;
 
    /* A utility function to check whether trees with roots
       as root1 and root2 are identical or not */
    boolean areIdentical(Node root1, Node root2)
    {
 
        /* base cases */
        if (root1 == null && root2 == null)
            return true;
 
        if (root1 == null || root2 == null)
            return false;
 
        /* Check if the data of both roots is same and data
           of left and right subtrees are also same */
        return (root1.data == root2.data
                && areIdentical(root1.left, root2.left)
                && areIdentical(root1.right, root2.right));
    }
 
    /* This function returns true if S is a subtree of T,
     * otherwise false */
    boolean isSubtree(Node T, Node S)
    {
        /* base cases */
        if (S == null)
            return true;
 
        if (T == null)
            return false;
 
        /* Check the tree with root as current node */
        if (areIdentical(T, S))
            return true;
 
        /* If the tree with root as current node doesn't
           match then
           try left and right subtrees one by one */
        return isSubtree(T.left, S)
            || isSubtree(T.right, S);
    }
 
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
 
        // TREE 1
        /* Construct the following tree
              26
             /   \
            10     3
           /    \     \
          4      6      3
           \
            30  */
 
        tree.root1 = new Node(26);
        tree.root1.right = new Node(3);
        tree.root1.right.right = new Node(3);
        tree.root1.left = new Node(10);
        tree.root1.left.left = new Node(4);
        tree.root1.left.left.right = new Node(30);
        tree.root1.left.right = new Node(6);
 
        // TREE 2
        /* Construct the following tree
           10
         /    \
         4      6
          \
          30  */
 
        tree.root2 = new Node(10);
        tree.root2.right = new Node(6);
        tree.root2.left = new Node(4);
        tree.root2.left.right = new Node(30);
 
        if (tree.isSubtree(tree.root1, tree.root2))
            System.out.println(
                "Tree 2 is subtree of Tree 1 ");
        else
            System.out.println(
                "Tree 2 is not a subtree of Tree 1");
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to check binary tree is a subtree of
# another tree
 
# A binary tree node
 
 
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# A utility function to check whether trees with roots
# as root 1 and root2 are indetical or not
 
 
def areIdentical(root1, root2):
 
    # Base Case
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
 
    # Check fi the data of both roots is same and data of
    # left and right subtrees are also same
    return (root1.data == root2.data and
            areIdentical(root1.left, root2.left)and
            areIdentical(root1.right, root2.right)
            )
 
# This function returns True if S is a subtree of T,
# otherwise False
 
 
def isSubtree(T, S):
 
    # Base Case
    if S is None:
        return True
 
    if T is None:
        return False
 
    # Check the tree with root as current node
    if (areIdentical(T, S)):
        return True
 
    # IF the tree with root as current node doesn't match
    # then try left and right subtree one by one
    return isSubtree(T.left, S) or isSubtree(T.right, S)
 
 
# Driver program to test above function
 
""" TREE 1
     Construct the following tree
              26
            /   \
          10     3
        /    \     \
      4      6      3
       \
        30
    """
 
T = Node(26)
T.right = Node(3)
T.right.right = Node(3)
T.left = Node(10)
T.left.left = Node(4)
T.left.left.right = Node(30)
T.left.right = Node(6)
 
""" TREE 2
     Construct the following tree
          10
        /    \
      4      6
       \
        30
    """
S = Node(10)
S.right = Node(6)
S.left = Node(4)
S.left.right = Node(30)
 
if isSubtree(T, S):
    print("Tree 2 is subtree of Tree 1")
else:
    print("Tree 2 is not a subtree of Tree 1")
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to check if binary tree
// is subtree of another binary tree
using System;
 
// A binary tree node
class Node {
    public int data;
    public Node left, right, nextRight;
 
    public Node(int item)
    {
        data = item;
        left = right = nextRight = null;
    }
}
 
public class BinaryTree {
    Node root1, root2;
 
    /* A utility function to check whether
        trees with roots as root1 and
        root2 are identical or not */
    bool areIdentical(Node root1, Node root2)
    {
 
        /* base cases */
        if (root1 == null && root2 == null)
            return true;
 
        if (root1 == null || root2 == null)
            return false;
 
        /* Check if the data of both roots is
        same and data of left and right
        subtrees are also same */
        return (root1.data == root2.data
                && areIdentical(root1.left, root2.left)
                && areIdentical(root1.right, root2.right));
    }
 
    /* This function returns true if S is
    a subtree of T, otherwise false */
    bool isSubtree(Node T, Node S)
    {
        /* base cases */
        if (S == null)
            return true;
 
        if (T == null)
            return false;
 
        /* Check the tree with root as current node */
        if (areIdentical(T, S))
            return true;
 
        /* If the tree with root as current
          node doesn't match then try left
          and right subtrees one by one */
        return isSubtree(T.left, S)
            || isSubtree(T.right, S);
    }
 
    // Driver code
    public static void Main()
    {
        BinaryTree tree = new BinaryTree();
 
        // TREE 1
        /* Construct the following tree
            26
            / \
            10 3
        / \ \
        4 6 3
        \
            30 */
 
        tree.root1 = new Node(26);
        tree.root1.right = new Node(3);
        tree.root1.right.right = new Node(3);
        tree.root1.left = new Node(10);
        tree.root1.left.left = new Node(4);
        tree.root1.left.left.right = new Node(30);
        tree.root1.left.right = new Node(6);
 
        // TREE 2
        /* Construct the following tree
        10
        / \
        4 6
        \
        30 */
 
        tree.root2 = new Node(10);
        tree.root2.right = new Node(6);
        tree.root2.left = new Node(4);
        tree.root2.left.right = new Node(30);
 
        if (tree.isSubtree(tree.root1, tree.root2))
            Console.WriteLine(
                "Tree 2 is subtree of Tree 1 ");
        else
            Console.WriteLine(
                "Tree 2 is not a subtree of Tree 1");
    }
}
 
/* This code is contributed by Rajput-Ji*/

Javascript

<script>
 
// JavaScript program to check if binary tree
// is subtree of another binary tree
  
// A binary tree node
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
        this.nextRight = null;
    }
}
  
var  root1,root2;
  
    /* A utility function to check whether
       trees with roots as root1 and
       root2 are identical or not */
    function areIdentical(root1,  root2) 
    {
  
        /* base cases */
        if (root1 == null && root2 == null)
            return true;
  
        if (root1 == null || root2 == null)
            return false;
  
        /* Check if the data of both roots
           is same and data of left and right
           subtrees are also same */
        return (root1.data == root2.data
                && areIdentical(root1.left, root2.left)
                && areIdentical(root1.right, root2.right));
    }
  
    /* This function returns true if S 
    is a subtree of T, otherwise false */
    function isSubtree(T,  S) 
    {
        /* base cases */
        if (S == null) 
            return true;
  
        if (T == null)
            return false;
  
        /* Check the tree with root as current node */
        if (areIdentical(T, S)) 
            return true;
  
        /* If the tree with root as
           current node doesn't match then
           try left and right subtrees one by one */
        return isSubtree(T.left, S)
                || isSubtree(T.right, S);
    }
  
          
        // TREE 1
        /* Construct the following tree
              26
             /   \
            10     3
           /    \     \
          4      6      3
           \
            30  */
           
        root1 = new Node(26);
        root1.right = new Node(3);
        root1.right.right = new Node(3);
        root1.left = new Node(10);
        root1.left.left = new Node(4);
        root1.left.left.right = new Node(30);
        root1.left.right = new Node(6);
  
        // TREE 2
        /* Construct the following tree
           10
         /    \
         4      6
          \
          30  */
           
        root2 = new Node(10);
        root2.right = new Node(6);
        root2.left = new Node(4);
        root2.left.right = new Node(30);
  
        if (isSubtree(root1, root2))
            document.write("Tree 2 is subtree of Tree 1 ");
        else
            document.write("Tree 2 is not a subtree of Tree 1");
 
 
// This code is contributed by todaysgaurav 
 
</script>

Output

Tree 2 is subtree of Tree 1

Time Complexity: O(M*N), Traversing on subtree S of size M for every N node of Tree T.
Auxiliary space: O(n)

The above problem can be solved in O(N) time. Please refer Check if a binary tree is subtree of another binary tree | Set 2 for O(N) solution.

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Check if a Binary Tree is subtree of another binary tree | Set 1

C++

C

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US