Solution: Build Binary Tree from Preorder and Inorder Traversal
Let's solve the Build Binary Tree from Preorder and Inorder Traversal problem using the Tree DepthFirst Search pattern.
We'll cover the following
Statement
Create a binary tree from two integer arrays, pOrder
and iOrder
, where pOrder
represents a preorder traversal of a binary tree, and iOrder
represents an inorder traversal of the same tree.
Constraints:
 $1 \leq$
pOrder.length
,iOrder.length
$\leq1000$ iOrder.length
$==$pOrder.length
 $1000 \leq$
pOrder[i]
,iOrder[i]
$\leq 1000$ pOrder
andiOrder
consist of unique values. Each value of
iOrder
also appears inpOrder
and vice versa.
Solution
To construct the binary tree from the given preorder and inorder traversals, we can use the preorder traversal to decide the root node of each subtree and inorder traversal to determine the left and right subtrees of that node.
In a preorder traversal, the root node of a tree is always visited before any of its children. Therefore, the first node in the preorder list is the root node of the entire tree. In an inorder traversal, the order of traversal is left, root, and then right. Therefore, the middle element will be the root, the element before the middle will be the left child, and the element after the middle will be the right child. So, we can use the inorder list to determine the left and right subtrees of this root node. We will search the node value in the inorder list, the elements before this value will create the left subtree of this node, and the elements after this value will create the right subtree of this node. We will recursively perform these steps to build the whole tree.
Letâ€™s create a recursive function that will perform the following steps:

Select the first element from the preorder list. Increment the preorder index,
pIndex
, to prepare for the next recursive call. 
Make a new tree node using the selected element as its data.

Find the index of the selected element in the inorder list,
iOrder
. The elements before thisinIndex
will be part of the left subtree of this node, and the elements after thisinIndex
will be part of the right subtree of this node. 
Make the following recursive call to add the elements from
left
toinIndex1
from the inorder list into the left subtree of the node.
root.left = buildTreeHelper(pOrder, iOrder, left, inIndex1, mapping, pIndex)
 Make the following recursive call to add the elements from
inIndex+1
toright
from the inorder list into the right subtree of the node.
root.right = buildTreeHelper(pOrder, iOrder, inIndex+1, right, mapping, pIndex)
 If
left > right
, it means there are no further elements in the list, and it will return NULL.
The following illustration depicts the steps above:
Level up your interview prep. Join Educative to access 80+ handson prep courses.