Make a Binary Tree from Given Inorder and Preorder Traveral.

Objective: Given a inorder and preorder traversal, construct a binary tree from that.

Input: Inorder and preorder traversals

Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal

Approach:

int [] inOrder = {2,5,6,10,12,14,15};

int [] preOrder = {10,5,2,6,14,12,15};

    • First element in preorder[] will be the root of the tree, here its 10.
    • Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
    • See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

  • See the picture and code.
Make-a-Binary-Tree-from-Given-Inorder-and-Preorder-Traveral

Make-a-Binary-Tree-from-Given-Inorder-and-Preorder-Traveral

Complete Code:


Output:

Constructed Tree : 
  2  5  6  10  12  14  15

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

  • anon.

    Broken method.

    No solution for —

    ADFGHKLPQRWZ(preorder)
    GFHKDLAWRQPZ(inorder)

    • Kavya S Muttur

      GKHFLDWRQZPA (Postorder)

%d bloggers like this: