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 Level Order Traversal

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

Input: Inorder and level order traversal

Appraoch:

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

int[] lev­el­Order = { 1, 2, 3, 4, 5, 6, 7 };

  • Last ele­ment in the lev­el­order [] 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 right­Sub­tree).
  • 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), but these X ele­ments will not be in the con­sec­u­tive in lev­el­order[] so we will extract these ele­ments from lev­el­order[] by main­tain­ing their sequence and store it in an array say newLeft­Level[].
  • 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), but these Y ele­ments will not be in the con­sec­u­tive in lev­el­order[] so we will extract these ele­ments from lev­el­order[] by main­tain­ing their sequence and store it in an array say newRightLevel[].
  • From pre­vi­ous two steps con­struct the left and right sub­tree and link it to root.left and root.right respec­tively by mak­ing recur­sive calls using newLeft­Level[] and newRightLevel[].
  • See the pic­ture for bet­ter explanation.
Construct-a-binary-tree-from-given-Inorder-and-Level-Order-Traversal

Construct-a-binary-tree-from-given-Inorder-and-Level-Order-Traversal

Com­plete Code:


Out­put:

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

You may also like...

  • Holden

    Great expla­na­tion! Thank you 🙂

    • Sumit

      Thanks Holden 🙂

  • Jayesh

    Nicely explained. What is the time com­plex­ity of program?

    • tuto­ri­al­hori­zon

      Worst case it would be O(n^3) . extract­ing the ele­ments in level order[] would be O(n^2) and one tra­ver­sal for inorder[]. I will update the post. Thanks Jayesh.

      • Jayesh

        I have one ques­tion. might be silly but would like to under­stand how Worst case time com­plex­ity would
        be O(n^3)? what I am get­ting is O(n^2). one tra­ver­sal for inorder[] doesn’t make it O(n^3).

        • tuto­ri­al­hori­zon

          Inorder tra­ver­sal takes O(n) time and for each node tra­ver­sal we are con­struct­ing new lev­el­order[] which takes O(n^2) time so total it takes O(n^3). Please cor­rect me if I m wrong.

  • Shiva

    Any bet­ter algo­rithm available?