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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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.