Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given two binary trees, check if one binary tree is a sub­tree of another

Input: Two binary trees

Out­put: True or false based on whether one tree is sub­tree of another

Exam­ple :

Tree is subtree of another tree example

Tree is sub­tree of another tree example

Approach:

We know that to inden­tity any binary tree can be rep­re­sented as the com­bi­na­tion of either inorder and pre­order tra­ver­sal OR inorder and pos­torder tra­ver­sal OR inorder and Level order traversal.

  • Say our trees are A and B.
  • Do the inorder trav­eral of treeA and store it in a String say inorderA.
  • Do the inorder trav­eral of treeB and store it in a String say inorderB.
  • Do the pos­torder trav­eral of treeA and store it in a String say postorderA.
  • Do the pos­torder trav­eral of treeB and store it in a String say postorderB.
  • Check if inorderA con­tains inorderB AND pos­torderA con­tains pos­torderB then it means treeB is a sub­tree of treeA.

Time Com­plex­ity : O(n)

Tree is subtree of another tree

Tree is sub­tree of another tree

Com­plete Code:


Out­put:

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

You may also like...

  • Alex

    Hi, I am just won­der­ing how you can prove that this solu­tion is correct.