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

Construct a binary tree from given Inorder and Postorder Traversal

Objec­tive: - Given a inorder and pos­torder tra­ver­sal, write an algo­rithm to con­struct a binary tree from that. This prob­lem was asked in the Microsoft cod­ing competition.

Input: Inorder and pos­torder traversals

Sim­i­lar Prob­lems: Make a Binary Tree from Given Inorder and Pre­order Traveral.

Appraoch:

int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };

int[] pos­tOrder = { 4, 5, 2, 6, 7, 3, 1 };.

  • Last ele­ment in the pos­torder [] will be the root of the tree, here it is 1.
  • Now the search ele­ment 1 in inorder[], say you find it at posi­tion i, once you find it, make note of ele­ments which are left to i (this will con­struct the left­sub­tree) and ele­ments which are right to i ( this will con­struct the rightSubtree).
  • Sup­pose in pre­vi­ous step, there are X num­ber of ele­ments which are left of ‘i’ (which will con­struct the left­sub­tree), take first X ele­ments from the pos­torder[] tra­ver­sal, this will be the post order tra­ver­sal for ele­ments which are left to i. sim­i­larly if there are Y num­ber of ele­ments which are right of ‘i’ (which will con­struct the right­sub­tree), take next Y ele­ments, after X ele­ments from the pos­torder[] tra­ver­sal, this will be the post order tra­ver­sal for ele­ments which are right to i
  • From pre­vi­ous two steps con­struct the left and right sub­tree and link it to root.left and root.right respectively.
  • See the pic­ture for bet­ter explanation.

    Construct-tree-from-Inorder-and-postorder-traversal

    Construct-tree-from-Inorder-and-postorder-traversal

Com­plete Code:


Out­put:

inorder traversal of constructed tree : 
  4  2  5  1  6  3  7

You may also like...

  • Kabir Sahni

    good work!is the worst case com­plex­ity O(n^2)?