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
\
30Tree 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 checkwhether trees with roots as root1 androot2 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 Sis 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 allocatesa new node with the given dataand 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 nodeclass 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 nodeclass 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 notdef 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 Falsedef 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 treeusing System;// A binary tree nodeclass 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 nodeclass 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
