Solution: Build Binary Tree from Preorder and Inorder Traversal

Statement#

Create a binary tree from two integer arrays, p_order and i_order, where p_order represents a preorder traversal of a binary tree, and i_order represents an inorder traversal of the same tree.

Constraints:

• $1 \leq$ p_order.length, i_order.length $\leq1000$
• i_order.length $==$ p_order.length
• $-1000 \leq$ p_order[i], i_order[i] $\leq 1000$
• p_order and i_order consist of unique values.
• Each value of i_order also appears in p_order 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:

1. Select the first element from the preorder list. Increment the preorder index, p_index, to prepare for the next recursive call.

2. Make a new tree node using the selected element as its data.

3. Find the index of the selected element in the inorder list, i_order. The elements before this in_index will be part of the left subtree of this node, and the elements after this in_index will be part of the right subtree of this node.

4. Make the following recursive call to add the elements from left to in_index-1 from the inorder list into the left subtree of the node.

root.left = build_tree_helper(p_order, i_order, left, in_index-1, mapping, p_index)

5. Make the following recursive call to add the elements from in_index+1 to right from the inorder list into the right subtree of the node.

root.right = build_tree_helper(p_order, i_order, in_index+1, right, mapping, p_index)

6. 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:

Let’s look at the code for this solution below:

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the number of elements in the preorder or inorder array.

Space complexity#

The space complexity of this solution is $O(n)$, where $n$ is the number of elements stored in the map.

Note: Using the hash map to store the inorder list will reduce the time complexity of the search to $O(1)$. It would otherwise take $O(n)$ in the case of a list.