Construct a binary tree from given Inorder and Postorder Traversal

Objective: Given a inorder and postorder traversal, write an algorithm to construct a binary tree from that. This problem was asked in the Microsoft coding competition.

Input: Inorder and postorder traversals

Similar Problems: Make a Binary Tree from Given Inorder and Preorder Traveral.

Appraoch:

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

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

  • Last element in the postorder [] 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).
  • Suppose in previous step, there are X number of elements which are left of ‘i’ (which will construct the leftsubtree), take first X elements from the postorder[] traversal, this will be the post order traversal for elements which are left to i. similarly if there are Y number of elements which are right of ‘i’ (which will construct the rightsubtree), take next Y elements, after X elements from the postorder[] traversal, this will be the post order traversal for elements which are right to i
  • From previous two steps construct the left and right subtree and link it to root.left and root.right respectively.
  • See the picture for better explanation.

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

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

Complete Code:


Output:

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

__________________________________________________
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.
__________________________________________________

  • Kabir Sahni

    good work!is the worst case complexity O(n^2)?

%d bloggers like this: