Given two binary trees, check if one binary tree is a subtree of another

Objective: Given two binary trees, check if one binary tree is a subtree of another

Input: Two binary trees

Output: True or false based on whether one tree is subtree of another

Example :

Tree is subtree of another tree example
Tree is subtree of another tree example

Approach:

We know that to indentity any binary tree can be represented as the combination of either inorder and preorder traversal OR inorder and postorder traversal OR inorder and Level order traversal.

  • Say our trees are A and B.
  • Do the inorder traveral of treeA and store it in a String say inorderA.
  • Do the inorder traveral of treeB and store it in a String say inorderB.
  • Do the postorder traveral of treeA and store it in a String say postorderA.
  • Do the postorder traveral of treeB and store it in a String say postorderB.
  • Check if inorderA contains inorderB AND postorderA contains postorderB then it means treeB is a subtree of treeA.

Time Complexity : O(n)

Tree is subtree of another tree
Tree is subtree of another tree

Complete Code:

public class BinarytreeisSubTreeOfAnother {
//store the inOrder and postorder traversal for both the array,
//if one array is the sub array of another array, that means one tree is the subtree of another one
public String inOrder(Node root, String i){
if(root!=null){
return inOrder(root.left,i) + " " + root.data + " " +inOrder(root.right,i);
}
return "";
}
public String postOrder(Node root, String i){
if(root!=null){
return postOrder(root.left,i) + " " + postOrder(root.right,i) + " " + root.data;
}
return "";
}
public boolean checkSubtree(Node rootA, Node rootB){
String inOrderA = inOrder(rootA,"");
String inOrderB = inOrder(rootB,"");
String postOrderA = postOrder(rootA,"");
String postOrderB = postOrder(rootB,"");
return (inOrderA.toLowerCase().contains(inOrderB.toLowerCase()) && postOrderA.toLowerCase().contains(postOrderB.toLowerCase()));
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main (String[] args) throws java.lang.Exception
{
Node rootA = new Node(1);
rootA.left = new Node(2);
rootA.right = new Node(4);
rootA.left.left = new Node(3);
rootA.right.right = new Node(6);
rootA.right.left = new Node(5);
Node rootB = new Node(4);
rootB.left = new Node(5);
rootB.right = new Node(6);
BinarytreeisSubTreeOfAnother i = new BinarytreeisSubTreeOfAnother();
System.out.print(" Tree A : ");
i.display(rootA);
System.out.println();
System.out.print(" Tree B : ");
i.display(rootB);
System.out.println();
System.out.println(i.checkSubtree(rootA,rootB));
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}

Output:

Tree A : 3 2 1 5 4 6
Tree B : 5 4 6
true

1 thought on “Given two binary trees, check if one binary tree is a subtree of another”

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.