Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T.
For Example:
Input:
Tree T -
1
/ \
2 3
/ \ / \
4 5 6 7
Tree S -
2
/ \
4 5
Output: YES
Explanation:
The above tree is the subtree of the tree T,
Hence the output is YES
Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each node of the tree that Pre-order traversal of that tree is the same as the Pre-order Traversal of the tree S with taking care of Null values that is by including the Null values in the Traversal list, because if the null values are not taken care then two different trees can have same pre-order traversal. Such as in the case of below trees –
1 1
/ \ / \
2 N N 2
/ \ / \
N N N N
Pre-order Traversal of both the trees will be -
{1, 2} - In case of without taking care of null values
{1, 2, N, N, N} and {1, N, 2, N, N}
In case of taking care of null values.
Algorithm:
- Declare a stack, to keep track of the left and right child of the nodes.
- Push the root node of the tree T.
- Run a loop while the stack is not empty and then check that if the pre-order traversal of the top node of the stack is the same, then return true.
- If the pre-order traversal does not match with the tree then pop the top node from the stack and push its left and right child of the popped node.
Below is the implementation of the above approach:
C++
// C++ implementation to check// if a tree is a subtree of // another binary tree#include <bits/stdc++.h>using namespace std;// Structure of the // binary tree nodestruct Node { int data; struct Node* left; struct Node* right;};// Function to create // new node Node* newNode(int x){ Node* temp = (Node*)malloc( sizeof(Node)); temp->data = x; temp->left = NULL; temp->right = NULL; return temp;}// Function to check if two trees// have same pre-order traversalbool areTreeIdentical(Node* t1, Node* t2){ stack<Node*> s1; stack<Node*> s2; Node* temp1; Node* temp2; s1.push(t1); s2.push(t2); // Loop to iterate over the stacks while (!s1.empty() && !s2.empty()) { temp1 = s1.top(); temp2 = s2.top(); s1.pop(); s2.pop(); // Both are None // hence they are equal if (temp1 == NULL && temp2 == NULL) continue; // nodes are unequal if ((temp1 == NULL && temp2 != NULL) || (temp1 != NULL && temp2 == NULL)) return false; // nodes have unequal data if (temp1->data != temp2->data) return false; s1.push(temp1->right); s2.push(temp2->right); s1.push(temp1->left); s2.push(temp2->left); } // if both tree are identical // both stacks must be empty. if (s1.empty() && s2.empty()) return true; else return false;}// Function to check if the Tree s// is the subtree of the Tree Tbool isSubTree(Node* s, Node* t){ // first we find the root of s in t // by traversing in pre order fashion stack<Node*> stk; Node* temp; stk.push(t); while (!stk.empty()) { temp = stk.top(); stk.pop(); // if current node data is equal // to root of s then if (temp->data == s->data) { if (areTreeIdentical(s, temp)) return true; } if (temp->right) stk.push(temp->right); if (temp->left) stk.push(temp->left); } return false;}// Driver Codeint main(){ /* 1 / \ 2 3 / \ / \ 4 5 6 7 */ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); /* 2 / \ 4 5 */ Node* root2 = newNode(2); root2->left = newNode(4); root2->right = newNode(5); if (isSubTree(root2, root)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation to check// if a tree is a subtree of // another binary treeimport java.util.*;class GFG{ // Structure of the // binary tree nodestatic class Node { int data; Node left; Node right;}; // Function to create // new node static Node newNode(int x){ Node temp = new Node(); temp.data = x; temp.left = null; temp.right = null; return temp;}// Function to check if two trees// have same pre-order traversalstatic boolean areTreeIdentical(Node t1, Node t2){ Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); Node temp1; Node temp2; s1.add(t1); s2.add(t2); // Loop to iterate over the stacks while (!s1.isEmpty() && !s2.isEmpty()) { temp1 = s1.peek(); temp2 = s2.peek(); s1.pop(); s2.pop(); // Both are None // hence they are equal if (temp1 == null && temp2 == null) continue; // nodes are unequal if ((temp1 == null && temp2 != null) || (temp1 != null && temp2 == null)) return false; // nodes have unequal data if (temp1.data != temp2.data) return false; s1.add(temp1.right); s2.add(temp2.right); s1.add(temp1.left); s2.add(temp2.left); } // if both tree are identical // both stacks must be empty. if (s1.isEmpty() && s2.isEmpty()) return true; else return false;}// Function to check if the Tree s// is the subtree of the Tree Tstatic boolean isSubTree(Node s, Node t){ // first we find the root of s in t // by traversing in pre order fashion Stack<Node> stk = new Stack<Node>(); Node temp; stk.add(t); while (!stk.isEmpty()) { temp = stk.peek(); stk.pop(); // if current node data is equal // to root of s then if (temp.data == s.data) { if (areTreeIdentical(s, temp)) return true; } if (temp.right != null) stk.add(temp.right); if (temp.left != null) stk.add(temp.left); } return false;} // Driver Codepublic static void main(String[] args){ /* 1 / \ 2 3 / \ / \ 4 5 6 7 */ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); /* 2 / \ 4 5 */ Node root2 = newNode(2); root2.left = newNode(4); root2.right = newNode(5); if (isSubTree(root2, root)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to check# if a tree is a subtree of# another binary tree# Structure of the# binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to check if two trees# have same pre-order traversaldef areTreeIdentical(t1 : Node, t2 : Node) -> bool: s1 = [] s2 = [] s1.append(t1) s2.append(t2) # Loop to iterate # over the stacks while s1 and s2: temp1 = s1.pop() temp2 = s2.pop() # Both are None # hence they are equal if (temp1 is None and temp2 is None): continue # Nodes are unequal if ((temp1 is None and temp2 is not None) or (temp1 is not None and temp2 is None)): return False # Nodes have unequal data if (temp1.data != temp2.data): return False s1.append(temp1.right) s2.append(temp2.right) s1.append(temp1.left) s2.append(temp2.left) # If both tree are identical # both stacks must be empty. if s1 and s2: return False return True# Function to check if the Tree s# is the subtree of the Tree Tdef isSubTree(s : Node, t : Node) -> Node: # First we find the # root of s in t # by traversing in # pre order fashion stk = [] stk.append(t) while stk: temp = stk.pop() # If current node data is equal # to root of s then if (temp.data == s.data): if (areTreeIdentical(s, temp)): return True if (temp.right): stk.append(temp.right) if (temp.left): stk.append(temp.left) return False# Driver Codeif __name__ == "__main__": ''' 1 / \ 2 3 / \ / \ 4 5 6 7 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) ''' 2 / \ 4 5 ''' root2 = Node(2) root2.left = Node(4) root2.right = Node(5) if (isSubTree(root2, root)): print("Yes") else: print("No")# This code is contributed by sanjeev2552 |
C#
// C# implementation to check// if a tree is a subtree of // another binary treeusing System;using System.Collections.Generic;class GFG{ // Structure of the // binary tree nodeclass Node { public int data; public Node left; public Node right;}; // Function to create // new node static Node newNode(int x){ Node temp = new Node(); temp.data = x; temp.left = null; temp.right = null; return temp;} // Function to check if two trees// have same pre-order traversalstatic bool areTreeIdentical(Node t1, Node t2){ Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); Node temp1; Node temp2; s1.Push(t1); s2.Push(t2); // Loop to iterate over the stacks while (s1.Count != 0 && s2.Count != 0) { temp1 = s1.Peek(); temp2 = s2.Peek(); s1.Pop(); s2.Pop(); // Both are None // hence they are equal if (temp1 == null && temp2 == null) continue; // nodes are unequal if ((temp1 == null && temp2 != null) || (temp1 != null && temp2 == null)) return false; // nodes have unequal data if (temp1.data != temp2.data) return false; s1.Push(temp1.right); s2.Push(temp2.right); s1.Push(temp1.left); s2.Push(temp2.left); } // if both tree are identical // both stacks must be empty. if (s1.Count == 0 && s2.Count == 0) return true; else return false;}// Function to check if the Tree s// is the subtree of the Tree Tstatic bool isSubTree(Node s, Node t){ // first we find the root of s in t // by traversing in pre order fashion Stack<Node> stk = new Stack<Node>(); Node temp; stk.Push(t); while (stk.Count != 0) { temp = stk.Peek(); stk.Pop(); // if current node data is equal // to root of s then if (temp.data == s.data) { if (areTreeIdentical(s, temp)) return true; } if (temp.right != null) stk.Push(temp.right); if (temp.left != null) stk.Push(temp.left); } return false;} // Driver Codepublic static void Main(String[] args){ /* 1 / \ 2 3 / \ / \ 4 5 6 7 */ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); /* 2 / \ 4 5 */ Node root2 = newNode(2); root2.left = newNode(4); root2.right = newNode(5); if (isSubTree(root2, root)) Console.Write("Yes"); else Console.Write("No");}} // This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to check// if a tree is a subtree of // another binary tree// Structure of the // binary tree nodeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }}; // Function to create // new node function newNode(x){ var temp = new Node(); temp.data = x; temp.left = null; temp.right = null; return temp;} // Function to check if two trees// have same pre-order traversalfunction areTreeIdentical(t1, t2){ var s1 = []; var s2 = []; var temp1 = null; var temp2 = null; s1.push(t1); s2.push(t2); // Loop to iterate over the stacks while (s1.length != 0 && s2.length != 0) { temp1 = s1[s1.length - 1]; temp2 = s2[s2.length - 1]; s1.pop(); s2.pop(); // Both are None // hence they are equal if (temp1 == null && temp2 == null) continue; // Nodes are unequal if ((temp1 == null && temp2 != null) || (temp1 != null && temp2 == null)) return false; // Nodes have unequal data if (temp1.data != temp2.data) return false; s1.push(temp1.right); s2.push(temp2.right); s1.push(temp1.left); s2.push(temp2.left); } // If both tree are identical // both stacks must be empty. if (s1.length == 0 && s2.length == 0) return true; else return false;}// Function to check if the Tree s// is the subtree of the Tree Tfunction isSubTree(s, t){ // First we find the root of s in t // by traversing in pre order fashion var stk = []; var temp; stk.push(t); while (stk.length != 0) { temp = stk[stk.length - 1]; stk.pop(); // If current node data is equal // to root of s then if (temp.data == s.data) { if (areTreeIdentical(s, temp)) return true; } if (temp.right != null) stk.push(temp.right); if (temp.left != null) stk.push(temp.left); } return false;} // Driver Code/* 1 / \ 2 3 / \ / \ 4 5 6 7*/var root = newNode(1);root.left = newNode(2);root.right = newNode(3);root.left.left = newNode(4);root.left.right = newNode(5);root.right.left = newNode(6);root.right.right = newNode(7);/* 2 / \ 4 5*/var root2 = newNode(2);root2.left = newNode(4);root2.right = newNode(5);if (isSubTree(root2, root)) document.write("Yes");else document.write("No"); // This code is contributed by rutvik_56</script> |
Output:
Yes
Time complexity: O(N) where N is no of nodes in a binary tree
Auxiliary Space: O(N)
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!
