Program to check if a binary tree is subtree of another binary tree

  • Write a C program to check if one binary tree is subtree of another binary tree using recursion.

Given two binary tree, we have to check whether one binary tree is subtree of another binary tree. A binary tree T is said to be the sub tree of another binary tree T2, if a tree rooted at any of the nodes of T2 is identical to T1. We will traverse every node of T2 and compare T1 with the sub tree rooted at every node of T2.

Two trees are identical if, both contains same set of nodes and the relative arrangement of nodes in both trees are also same.
Algorithm to check if one binary tree is subtree of another binary tree
Let "root1" and "root2" be the root nodes of two binary tree T1 and T2 respectively. We want to check whether T2 is subtree of T1 or not.
  • If root2 is equal to NULL, then return true because an empty tree is sub tree of all binary tree.
  • If root1 is equal to NULL, then return false.
  • Check if the subtree rooted at root1 is identical to T2, If yes then return true.
  • Else, recursively check whether T2 is sub tree of left or right subtree of root1.
Time Complexity : O(mn), where m and n are the number of nodes in both trees.

C program to check whether one binary tree is subtree of another binary tree

#include <stdio.h>

#define TRUE 1
#define FALSE 0

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      / \       
     8  9       
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);

    root->left = getNewNode(2);
    root->right = getNewNode(3);

    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);

    root->left->left->left = getNewNode(8);
    root->left->left->right = getNewNode(9);
    
    return root;
}

/*
 Checks, if two trees are same or not  
*/
int isIdentical(struct node *first, struct node *second){
    /*If both are NULL , then Identical */
    if(first == NULL && second == NULL)
        return TRUE;
    /* If only one tree is NULL, then not Identical */
    if(first == NULL || second == NULL)
        return FALSE;
     
    /* IF left sub-trees, right subtrees and root node of 
    both trees are same then both trees are identical */
    if(isIdentical(first->left, second->left) && 
       isIdentical(first->right, second->right) && 
       first->data == second->data){
           return TRUE;
    } else {
        return FALSE;
    }
}

/* This function check whether second is a subtree of first or not.  */
int checkSubTree(struct node *first, struct node *second) {
    /* Recursion termination condition  */
    if (second == NULL)
        return TRUE;
 
    if(first == NULL)
        return FALSE;
 
    /* Check if tree with first as root is 
    same as tree with second as root node  */
    if(isIdentical(first, second)){
     return TRUE;
    }
 
    /* Recursively check, If left and right 
    subtree of first is same as second*/
    return checkSubTree(first->left, second) ||
      checkSubTree(first->right, second);
}

int main() {
    struct node *root = generateBTree();
    struct node *subtree = root->left;
    
    /* Printing ancestor's of nodes */
    if(checkSubTree(root, subtree)){
     printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }
    
    getchar();
    return 0; 
}
Output
TRUE
Posted by
Labels: