# 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 :

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)

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”

1. Hi, I am just wondering how you can prove that this solution is correct.