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-T Tree-S
1 3
/ \ /
2 3 6
/ \ /
4 5 6
Output: Yes
Explanation:
Height of a Tree-S is -2
In the Tree-T the nodes with height 2 are -{2 ,3}
In the nodes {2,3} the nodes which satisfy the identical subtree with tree-S are {3}
So, there exists a identical subtree i.e tree-S in the tree-TInput: Tree-T Tree-S
26 10
/ \ / \
10 3 4 6
/ \ \ \
4 6 3 30
\
30
Naive Approach: The naive approach is discussed in Set-1 of this problem.
Efficient Approach: The efficient approach based on uniquely identifying a tree from their inorder and preorder/postorder traversal is discussed in Set-2 of this problem.
Alternative Efficient Approach: The approach is to find all nodes at the same height as the height of Tree-S in Tree-T and then compare.
- Initially calculate the height of the given subtree(Tree -S).
- In the next step, find all the nodes from Tree-T which are having height as the height of the Tree-S, and store their address.
- Then from every node, we stored we check if that is an identical subtree or not.
- In this approach, there is no need to check for all the nodes whether it is an identical subtree or not as we have height as a parameter at which actually identical subtree validation must be performed.
Below is the implementation of the above.
C++
// C++ program to check if a binary tree// Is subtree of another binary tree#include <bits/stdc++.h>using namespace std;// Structure of a Binary Tree Nodestruct Node { int data; struct Node *left, *right;};// Utility function to// Create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to calculate// The height of the treeint height_of_tree(Node* root){ if (!root) return 0; // Calculate the left subtree // And right subtree height int left = height_of_tree(root->left); int right = height_of_tree(root->right); return 1 + max(left, right);}// Function to check// It is a subtree or notbool CheckSubTree(Node* T, Node* S){ if (S == NULL && T == NULL) return true; if (T == NULL || S == NULL) return false; if (T->data != S->data) return false; return CheckSubTree(T->left, S->left) && CheckSubTree(T->right, S->right);}// Function to extract the// nodes of height of the subtree// i.e tree-S from the parent// tree(T-tree) using the height of the treeint subtree_height(Node* root, vector<Node*>& nodes, int h){ if (root == NULL) return 0; else { // Calculating the height // Of the tree at each node int left = subtree_height(root->left, nodes, h); int right = subtree_height(root->right, nodes, h); int height = max(left, right) + 1; // If height equals to height // of the subtree then store it if (height == h) nodes.push_back(root); return height; }}// Function to check if it is a subtreebool isSubTree(Node* T, Node* S){ if (T == NULL && S == NULL) return true; if (T == NULL || S == NULL) return false; // Calling the height_of_tree // Function to calculate // The height of subtree-S int h = height_of_tree(S); vector<Node*> nodes; // Calling the subtree_height // To extract all the nodes // Of height of subtree(S) i.e height-h int h1 = subtree_height(T, nodes, h); bool result = false; int n = nodes.size(); for (int i = 0; i < n; i++) { // If the data of the // node of tree-T at height-h // is equal to the data // of root of subtree-S // then check if is a subtree // of the parent tree or not if (nodes[i]->data == S->data) result = CheckSubTree(nodes[i], S); // If any node is satisfying // the CheckSubTree then return true if (result) return true; } // If no node is satisfying // the subtree the return false return false;}// Driver programint main(){ // Create binary tree T in above diagram Node* T = newNode(1); T->left = newNode(2); T->right = newNode(3); T->left->left = newNode(4); T->left->right = newNode(5); T->right->left = newNode(6); // Create binary tree S shown in diagram Node* S = newNode(3); S->left = newNode(6); // Lets us call the function // isSubTree() which checks // that the given Tree -S is a subtree // of tree -T(parent tree) if (isSubTree(T, S)) cout << "Yes" << endl; else cout << "No" << endl; return 0;} |
Java
// Java program to check if a binary tree// Is subtree of another binary treeimport java.util.*;class GFG{// Structure of a Binary Tree Nodestatic class Node { int data; Node left, right;};static Vector<Node> nodes = new Vector<Node>(); // Utility function to// Create a new tree nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to calculate// The height of the treestatic int height_of_tree(Node root){ if (root == null) return 0; // Calculate the left subtree // And right subtree height int left = height_of_tree(root.left); int right = height_of_tree(root.right); return 1 + Math.max(left, right);}// Function to check// It is a subtree or notstatic boolean CheckSubTree(Node T, Node S){ if (S == null && T == null) return true; if (T == null || S == null) return false; if (T.data != S.data) return false; return CheckSubTree(T.left, S.left) && CheckSubTree(T.right, S.right);}// Function to extract the// nodes of height of the subtree// i.e tree-S from the parent// tree(T-tree) using the height of the treestatic int subtree_height(Node root, int h){ if (root == null) return 0; else { // Calculating the height // Of the tree at each node int left = subtree_height(root.left, h); int right = subtree_height(root.right, h); int height = Math.max(left, right) + 1; // If height equals to height // of the subtree then store it if (height == h) nodes.add(root); return height; }}// Function to check if it is a subtreestatic boolean isSubTree(Node T, Node S){ if (T == null && S == null) return true; if (T == null || S == null) return false; // Calling the height_of_tree // Function to calculate // The height of subtree-S int h = height_of_tree(S); // Calling the subtree_height // To extract all the nodes // Of height of subtree(S) i.e height-h int h1 = subtree_height(T, h); boolean result = false; int n = nodes.size(); for (int i = 0; i < n; i++) { // If the data of the // node of tree-T at height-h // is equal to the data // of root of subtree-S // then check if is a subtree // of the parent tree or not if (nodes.get(i).data == S.data) result = CheckSubTree(nodes.get(i), S); // If any node is satisfying // the CheckSubTree then return true if (result) return true; } // If no node is satisfying // the subtree the return false return false;}// Driver programpublic static void main(String[] args){ // Create binary tree T in above diagram Node T = newNode(1); T.left = newNode(2); T.right = newNode(3); T.left.left = newNode(4); T.left.right = newNode(5); T.right.left = newNode(6); // Create binary tree S shown in diagram Node S = newNode(3); S.left = newNode(6); // Lets us call the function // isSubTree() which checks // that the given Tree -S is a subtree // of tree -T(parent tree) if (isSubTree(T, S)) System.out.print("Yes" +"\n"); else System.out.print("No" +"\n");}}// This code is contributed by shikhasingrajput |
Python3
# Python program to check if a binary tree# Is subtree of another binary tree# Structure of a Binary Tree Nodefrom platform import nodeclass Node: def __init__(self,data): self.data = data self.left = self.right = None # Utility function to# Create a new tree nodedef newNode(data): temp = Node(data) return temp# Function to calculate# The height of the treedef height_of_tree(root): if (root == None): return 0 # Calculate the left subtree # And right subtree height left = height_of_tree(root.left) right = height_of_tree(root.right) return 1 + max(left, right)# Function to check# It is a subtree or notdef CheckSubTree(T, S): if (S == None and T == None): return True if (T == None or S == None): return False if (T.data != S.data): return False return CheckSubTree(T.left, S.left) and CheckSubTree(T.right, S.right)# Function to extract the# nodes of height of the subtree# i.e tree-S from the parent# tree(T-tree) using the height of the treedef subtree_height(root,nodes,h): if (root == None): return 0 else: # Calculating the height # Of the tree at each node left = subtree_height(root.left,nodes, h) right = subtree_height(root.right, nodes, h) height = max(left, right) + 1 # If height equals to height # of the subtree then store it if (height == h): nodes.append(root) return height# Function to check if it is a subtreedef isSubTree(T, S): if (T == None and S == None): return True if (T == None or S == None): return False # Calling the height_of_tree # Function to calculate # The height of subtree-S h = height_of_tree(S) nodes = [] # Calling the subtree_height # To extract all the nodes # Of height of subtree(S) i.e height-h h1 = subtree_height(T, nodes, h) result = False n = len(nodes) for i in range(n): # If the data of the # node of tree-T at height-h # is equal to the data # of root of subtree-S # then check if is a subtree # of the parent tree or not if (nodes[i].data == S.data): result = CheckSubTree(nodes[i], S) # If any node is satisfying # the CheckSubTree then return true if (result): return True # If no node is satisfying # the subtree the return false return False# Driver program# Create binary tree T in above diagramT = newNode(1)T.left = newNode(2)T.right = newNode(3)T.left.left = newNode(4)T.left.right = newNode(5)T.right.left = newNode(6)# Create binary tree S shown in diagramS = newNode(3)S.left = newNode(6)# Lets us call the function# isSubTree() which checks# that the given Tree -S is a subtree# of tree -T(parent tree)if (isSubTree(T, S)): print("Yes")else: print("No")# This code is contributed by shinjanpatra |
C#
// C# program to check if a binary tree// Is subtree of another binary treeusing System;using System.Collections.Generic;// Structure of a Binary Tree Nodepublic class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = null; right = null; }}public class GFG { // Utility function to // Create a new tree node public static Node newNode(int data) { Node temp = new Node(data); return temp; } // Function to calculate // The height of the tree public static int height_of_tree(Node root) { if (root == null) return 0; // Calculate the left subtree // And right subtree height int left = height_of_tree(root.left); int right = height_of_tree(root.right); return 1 + Math.Max(left, right); } // Function to check // It is a subtree or not public static bool CheckSubTree(Node T, Node S) { if (S == null && T == null) return true; if (T == null || S == null) return false; if (T.data != S.data) return false; return CheckSubTree(T.left, S.left) && CheckSubTree(T.right, S.right); } // Function to extract the // nodes of height of the subtree // i.e tree-S from the parent // tree(T-tree) using the height of the tree public static int subtree_height(Node root, List<Node> nodes, int h) { if (root == null) return 0; else { // Calculating the height // Of the tree at each node int left = subtree_height(root.left, nodes, h); int right = subtree_height(root.right, nodes, h); int height = Math.Max(left, right) + 1; // If height equals to height // of the subtree then store it if (height == h) nodes.Add(root); return height; } } // Function to check if it is a subtree public static bool isSubTree(Node T, Node S) { if (T == null && S == null) return true; if (T == null || S == null) return false; // Calling the height_of_tree // Function to calculate // The height of subtree-S int h = height_of_tree(S); List<Node> nodes = new List<Node>(); // Calling the subtree_height // To extract all the nodes // Of height of subtree(S) i.e height-h int h1 = subtree_height(T, nodes, h); bool result = false; int n = nodes.Count; for (int i = 0; i < n; i++) { // If the data of the // node of tree-T at height-h // is equal to the data // of root of subtree-S // then check if is a subtree // of the parent tree or not if (nodes[i].data == S.data) result = CheckSubTree(nodes[i], S); // If any node is satisfying // the CheckSubTree then return true if (result) return true; } // If no node is satisfying // the subtree the return false return false; } // Driver program public static void Main() { // Create binary tree T in above diagram Node T = newNode(1); T.left = newNode(2); T.right = newNode(3); T.left.left = newNode(4); T.left.right = newNode(5); T.right.left = newNode(6); // Create binary tree S shown in diagram Node S = newNode(3); S.left = newNode(6); // Lets us call the function // isSubTree() which checks // that the given Tree -S is a subtree // of tree -T(parent tree) if (isSubTree(T, S)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by adityamaharshi21 |
Javascript
<script>// JavaScript program to check if a binary tree// Is subtree of another binary tree// Structure of a Binary Tree Nodeclass Node { constructor(data){ this.data = data; this.left = this.right = null; }};// Utility function to// Create a new tree nodefunction newNode(data){ let temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to calculate// The height of the treefunction height_of_tree(root){ if (!root) return 0; // Calculate the left subtree // And right subtree height let left = height_of_tree(root.left); let right = height_of_tree(root.right); return 1 + Math.max(left, right);}// Function to check// It is a subtree or notfunction CheckSubTree(T, S){ if (S == null && T == null) return true; if (T == null || S == null) return false; if (T.data != S.data) return false; return CheckSubTree(T.left, S.left) && CheckSubTree(T.right, S.right);}// Function to extract the// nodes of height of the subtree// i.e tree-S from the parent// tree(T-tree) using the height of the treefunction subtree_height(root,nodes,h){ if (root == null) return 0; else { // Calculating the height // Of the tree at each node let left = subtree_height(root.left, nodes, h); let right = subtree_height(root.right, nodes, h); let height = Math.max(left, right) + 1; // If height equals to height // of the subtree then store it if (height == h) nodes.push(root); return height; }}// Function to check if it is a subtreefunction isSubTree(T, S){ if (T == null && S == null) return true; if (T == null || S == null) return false; // Calling the height_of_tree // Function to calculate // The height of subtree-S let h = height_of_tree(S); let nodes = []; // Calling the subtree_height // To extract all the nodes // Of height of subtree(S) i.e height-h let h1 = subtree_height(T, nodes, h); let result = false; let n = nodes.length; for (let i = 0; i < n; i++) { // If the data of the // node of tree-T at height-h // is equal to the data // of root of subtree-S // then check if is a subtree // of the parent tree or not if (nodes[i].data == S.data) result = CheckSubTree(nodes[i], S); // If any node is satisfying // the CheckSubTree then return true if (result) return true; } // If no node is satisfying // the subtree the return false return false;}// Driver program// Create binary tree T in above diagramlet T = newNode(1);T.left = newNode(2);T.right = newNode(3);T.left.left = newNode(4);T.left.right = newNode(5);T.right.left = newNode(6);// Create binary tree S shown in diagramlet S = newNode(3);S.left = newNode(6);// Lets us call the function// isSubTree() which checks// that the given Tree -S is a subtree// of tree -T(parent tree)if (isSubTree(T, S)) document.write("Yes");else document.write("No");// This code is contributed by shinjanpatra</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O( 2H ) where H is the height of Tree-T
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!
