• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Problem Statement:


Given an inorder and level order traversal, construct a binary tree from that.

Solution:



Let's take the below example:

Given input array inorder[] = { 4, 2, 5, 1, 6, 3, 7 }
Given input array levelOrder[] = { 1, 2, 3, 4, 5, 6, 7 }

  • First element in the levelorder [] 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), but these X elements will not be in the consecutive in levelorder[] so we will extract these elements from levelorder[] by maintaining their sequence and store it in an array say newLeftLevel[].
  • Similarly if there are Y number of elements which are right of ‘i’ (which will construct the rightsubtree), but these Y elements will not be in the consecutive in levelorder[] so we will extract these elements from levelorder[] by maintaining their sequence and store it in an array say newRightLevel[].
  • From previous two steps construct the left and right subtree and link it to root.left and root.right respectively by making recursive calls using newLeftLevel[] and newRightLevel[].

See the picture for better explanation.


Java code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python 2 code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Related Chapters:


  1. Tree Construction: Inorder - Preorder
  2. Tree Construction: Inorder - Postorder


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave