99. Construct a binary tree from given Inorder and Level Order Traversal

Objective: - Given an inorder and level order traversal

Approach:

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

  levelOrder [] = { 1, 2, 3, 4, 5, 6, 7 }

Start by identifying the root of the tree, which is the first element in the level order traversal array. For instance, if the root is 1, it will be at the beginning of the level order array.
Once you have found the root value in the inorder traversal array, denote its position as 'i'. This position 'i' divides the inorder traversal into two parts: elements to the left of 'i' will form the left subtree, and elements to the right of 'i' will form the right subtree.
Extract the elements that belong to the left subtree from the level order traversal array. Although these elements may not be consecutive in the level order array, maintain their sequence and store them in a new array, which we'll call newLeftLevel[].
Similarly, extract the elements for the right subtree from the level order traversal array. Store these elements in another new array, which we'll call newRightLevel[].
With the extracted elements from the previous steps, construct the left and right subtrees recursively. Link these subtrees to the root node's left and right children, respectively, by making recursive calls using the arrays newLeftLevel[] and newRightLevel[].
See the picture for a better explanation.

Output:

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