Check If A binary tree is a subtree in another binary tree (supertree)
The idea behind checking if a given binary tree is a subtree in another binary tree (supertree) is
- The supertree that we are searching in shouldn’t be empty / null.
- The structure of a given tree i.e the root, root’s left sub-tree, and root’s right-subtree are the same in the supertree.
- The left node of the given tree should be a leaf node in the supertree.
Example : Consider tree D with root ( 16 ) and right child ( 18 ).
Even though we see the same structure in the supertree, but tree D is not a subtree in the supertree as its leaf node 18 is not a leaf node in the supertree.
Thus we see,
Tree A is present as a subtree in the supertree.
Tree B is not present as a subtree in the supertree.
Tree C is present as a subtree in the supertree.
Tree D is not present as a subtree in the supertree.
Time complexity : O ( n m ) where ’n’ is the number of nodes in the supertree (i.e the tree that we are searching in) and ’m’ is the number of nodes in the tree being searched for.
Program for finding a binary subtree in a super tree
class Node :
def __init__(self, data=0, left=None, right=None) :
self.data = data
self.left = left
self.right = right
# Check if the 2 trees (subtree and super tree) are identical.
def AreTreesIdentical (root_super : Node, root_sub : Node) -> bool :
if (root_super == None and root_sub == None) :
return True
if (root_super == None or root_sub == None) :
return False
# These recursive calls return True if the left and right subtrees
# are identical and the nodes have same data
return ( AreTreesIdentical(root_super.left, root_sub.left) and
AreTreesIdentical(root_super.right, root_sub.right) and
(root_super.data == root_sub.data))
def FindBinarySubtree (root_super : Node, root_sub : Node) -> bool :
if (root_sub == None) :
return True
# Super tree: The tree in which we are searching for a subtree.
# If the super tree is empty the subtree definitely cannot be found
if (root_super == None) :
return False
if (AreTreesIdentical(root_super, root_sub) == True) :
return True
# Check for the subtree in the left and right part of the super tree.
return (FindBinarySubtree(root_super.left, root_sub) or
FindBinarySubtree(root_super.right, root_sub))
def main() :
# Constructed binary tree is
# 9
# / \
# 5 16
# / \ / \
# 3 7 12 18
# / \ \
# 6 8 25
# / \
# 20 36
#
node3 = Node(3)
node6 = Node(6)
node8 = Node(8)
node12 = Node(12)
node20 = Node(20)
node36 = Node(36)
node7 = Node(7, node6, node8)
node25 = Node(25, node20, node36)
node18 = Node(18, None, node25)
node16 = Node(16, node12, node18)
node5 = Node(5, node3, node7)
root_node9 = Node(9, node5, node16)
# Subtree
# 18
# \
# 25
# / \
# 20 36
_node20 = Node(20)
_node36 = Node(36)
_node25 = Node(25, _node20, _node36)
root_node18 = Node(18, None, node25)
# Subtree
# 7
# / \
# 6 8
# \
# 9
_node9 = Node(9)
_node6 = Node(6)
_node8 = Node(8, None, _node9)
root_node7 = Node(7, _node6, _node8)
# Subtree
# 16
# \
# 18
_node18 = Node(18)
root_node16 = Node(16, None, _node18)
# Subtree
# 3
root_node3 = Node(3)
subtree_roots_list = [root_node18, root_node7, root_node16, root_node3]
for subtree_root in (subtree_roots_list) :
if (FindBinarySubtree(root_node9, subtree_root) == True) :
print("Binary subtree with root " + str(subtree_root.data) \
+ " exist in binary tree with root " + str(root_node9.data))
else :
print("Binary subtree with root " + str(subtree_root.data) + \
" does not exist in binary tree with root " + str(root_node9.data))
if __name__ == "__main__" :
main()
Output
Binary subtree with root 18 exist in binary tree with root 9
Binary subtree with root 7 does not exist in binary tree with root 9
Binary subtree with root 16 does not exist in binary tree with root 9
Binary subtree with root 3 exist in binary tree with root 9
#include<iostream>
#include<vector>
using namespace std;
class Node {
public:
int data;
Node * left;
Node * right;
Node(int x, Node * left_node = nullptr, Node * right_node = nullptr) :
data(x), left(left_node), right(right_node)
{}
};
// Check if the 2 trees (subtree and super tree) are identical.
bool AreTreesIdentical (Node * root_super, Node * root_sub) {
if (root_super == nullptr && root_sub == nullptr)
return true;
if (root_super == nullptr || root_sub == nullptr)
return false;
/* These recursive calls return true if the left and right subtrees
are identical and the nodes have same data*/
return (AreTreesIdentical (root_super->left, root_sub->left) &&
AreTreesIdentical (root_super->right, root_sub->right) &&
(root_super->data == root_sub->data));
}
bool FindBinarySubtree (Node * root_super, Node * root_sub) {
if (root_sub == nullptr)
return true;
/* Super tree: The tree in which we are searching for a subtree.
If the super tree is empty the subtree definitely cannot be found */
if (root_super == nullptr)
return false;
if (AreTreesIdentical(root_super, root_sub))
return true;
// Check for the subtree in the left and right part of the super tree.
return (FindBinarySubtree (root_super->left, root_sub) ||
FindBinarySubtree (root_super->right, root_sub));
}
int main() {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node node3(3), node6(6), node8(8), node12(12), node20(20), node36(36);
Node node7(7, &node6, &node8);
Node node25(25, &node20, &node36);
Node node18(18, nullptr, &node25);
Node node16(16, &node12, &node18);
Node node5(5, &node3, &node7);
Node root_node9(9, &node5, &node16);
/* Subtree
18
\
25
/ \
20 36 */
Node _node20(20), _node36(36);
Node _node25(25, &_node20, &_node36);
Node root_node18(18, nullptr, &node25);
/* Subtree
7
/ \
6 8
\
9 */
Node _node9(9), _node6(6);
Node _node8(8, nullptr, &_node9);
Node root_node7(7, &_node6, &_node8);
/* Subtree
16
\
18 */
Node _node18(18);
Node root_node16(16, nullptr, &_node18);
/* Subtree
3 */
Node root_node3(3);
vector<Node> subtree_roots = { root_node18, root_node7, root_node16, root_node3 };
for (auto & subtree_root : subtree_roots) {
if (FindBinarySubtree(&root_node9, &subtree_root) == true){
cout << "Binary subtree with root " << subtree_root.data \
<< " exist in binary tree with root " << root_node9.data << endl;
} else {
cout << "Binary subtree with root " << subtree_root.data << \
" does not exist in binary tree with root " << root_node9.data << endl;
}
}
return 0;
}
Output
Binary subtree with root 18 exist in binary tree with root 9
Binary subtree with root 7 does not exist in binary tree with root 9
Binary subtree with root 16 does not exist in binary tree with root 9
Binary subtree with root 3 exist in binary tree with root 9
import java.util.List;
import java.util.Arrays;
class Node {
int data;
Node left;
Node right;
Node (int x) {
data = x;
left = null;
right = null;
}
Node (int x, Node left_node, Node right_node) {
data = x;
left = left_node;
right = right_node;
}
}
class BinTree {
// Check if the 2 trees (subtree and super tree) are identical.
boolean AreTreesIdentical (Node root_super, Node root_sub) {
if (root_super == null && root_sub == null)
return true;
if (root_super == null || root_sub == null)
return false;
/* These recursive calls return true if the left and right subtrees
are identical and the nodes have same data */
return (AreTreesIdentical(root_super.left, root_sub.left) &&
AreTreesIdentical(root_super.right, root_sub.right) &&
(root_super.data == root_sub.data));
}
boolean FindBinarySubtree (Node root_super, Node root_sub) {
if (root_sub == null)
return true;
/* Super tree: The tree in which we are searching for a subtree.
If the super tree is empty the subtree definitely cannot be found */
if (root_super == null)
return false;
if (AreTreesIdentical(root_super, root_sub) == true)
return true;
// Check for the subtree in the left and right part of the super tree.
return (FindBinarySubtree(root_super.left, root_sub) ||
FindBinarySubtree(root_super.right, root_sub));
}
public static void main (String[] args) {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node node3 = new Node(3);
Node node6 = new Node(6);
Node node8 = new Node(8);
Node node12 = new Node(12);
Node node20 = new Node(20);
Node node36 = new Node(36);
Node node7 = new Node(7, node6, node8);
Node node25 = new Node(25, node20, node36);
Node node18 = new Node(18, null, node25);
Node node16 = new Node(16, node12, node18);
Node node5 = new Node(5, node3, node7);
Node root_node9 = new Node(9, node5, node16);
/* Subtree
18
\
25
/ \
20 36 */
Node _node20 = new Node(20);
Node _node36 = new Node(36);
Node _node25 = new Node(25, _node20, _node36);
Node root_node18 = new Node(18, null, node25);
/* Subtree
7
/ \
6 8
\
9 */
Node _node9 = new Node(9);
Node _node6 = new Node(6);
Node _node8 = new Node(8, null, _node9);
Node root_node7 = new Node(7, _node6, _node8);
/* Subtree
16
\
18 */
Node _node18 = new Node(18);
Node root_node16 = new Node(16, null, _node18);
/* Subtree
3 */
Node root_node3 = new Node(3);
List<Node> subtree_roots = Arrays.asList (root_node18, root_node7, root_node16, root_node3);
BinTree b = new BinTree();
for (Node subtree_root : subtree_roots) {
if (b.FindBinarySubtree(root_node9, subtree_root) == true){
System.out.println ( "Binary subtree with root " + subtree_root.data
+ " exist in binary tree with root " + root_node9.data);
} else {
System.out.println ( "Binary subtree with root " + subtree_root.data +
" does not exist in binary tree with root " + root_node9.data);
}
}
}
}
Output
Binary subtree with root 18 exist in binary tree with root 9
Binary subtree with root 7 does not exist in binary tree with root 9
Binary subtree with root 16 does not exist in binary tree with root 9
Binary subtree with root 3 exist in binary tree with root 9