**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

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