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

Make a Binary Tree from Given Inorder and Preorder Traveral.

Objec­tive: - Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that.

Input: Inorder and pre­order traversals

Sim­i­lar Prob­lem: Con­struct a binary tree from given Inorder and Pos­torder Traversal

Approach:

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

int [] pre­Order = {10,5,2,6,14,12,15};

    • First ele­ment in pre­order[] will be the root of the tree, here its 10.
    • Now the search ele­ment 10 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).
    • See this step above and recur­sively con­struct left sub­tree and link it root.left and recur­sively con­struct right sub­tree and link it root.right.

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

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

Com­plete Code:


Out­put:

Constructed Tree : 
  2  5  6  10  12  14  15

You may also like...

  • anon.

    Bro­ken method.

    No solu­tion for —

    ADFGHKLPQRWZ(preorder)
    GFHKDLAWRQPZ(inorder)