Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

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:


Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • Alex

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

%d bloggers like this: