105. Construct Binary Tree from Preorder and Inorder Traversal

/**

 * 105. Construct Binary Tree from Preorder and Inorder Traversal

 * Given preorder and inorder traversal of a tree, construct the binary tree.

 * Note:

 * You may assume that duplicates do not exist in the tree.

 * For example, given

 * preorder = [3,9,20,15,7]

 * inorder = [9,3,15,20,7]

 * Return the following binary tree:

 *     3

 *    / \

 *   9  20

 *     /  \

 *    15   7

*/

See solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trees/CreateTreeFromPreAndInOrder.java

See here another very similar problem: https://github.com/zcoderz/leetcode/blob/main/src/main/java/binary_tree/InOrderPostOrderBuildTree.java

We can use the fact that the in-order traversal can be used to split the data in to right and left trees. And then leveraging the pre order to identify the root index for each next sub tree to construct the physical tree.

The algorithm is:

  1. Create a map that indicates the index of an inorder key in the index array.  
  2. Use the pre order index to identify the next sub tree’s root index
  3. Find the index of the subtree root calculated in 2, inside the map that was generated in 1.
  4. Repeat steps 2 and 3 for each of the left and right sub trees
    1. Change left bounds in recursion appropriately for left (left, index-1)
    2. Change right bounds in recursion appropriately for left (index+1, right)

Here is the solution for the code:

/**
 * construct a map based on in order coordinates of given indices
 * @param preorder
 * @param inorder
 * @return
 */
public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    this.inorder = inorder;

    // build a hashmap value -> its index
    int idx = 0;
    for (Integer val : inorder)
        idx_map.put(val, idx++);
    return helper(0, inorder.length-1);
}

/**
 *
 * Repeat below for each sub tree (Root, Left, Right), where repeat is done for left and right sub trees
 *   Preorder traversal follows Root -> Left -> Right order
 *   The first element in the preorder list is a root.
 *   Once you know the root, you can use the inorder list to split the array into left and right sub arrays
 * Use return of the repeat to stitch left and right child trees
 *
 * @param in_left
 * @param in_right
 * @return
*/
 public TreeNode helper(int in_left, int in_right) {
    // if there is no elements to construct subtrees
    if (in_left > in_right)
        return null;

    // pick up pre_idx element as a root
    int root_val = preorder[pre_idx];
    TreeNode root = new TreeNode(root_val);

    // root splits inorder list
    // into left and right subtrees
    int index = idx_map.get(root_val);

    // move to the next pre order root
    pre_idx++;
    // build left subtree
    root.left = helper(in_left, index-1);
    // build right subtree
    root.right = helper(index + 1, in_right);
    return root;
}