Construct Binary Tree from Preorder and Inorder Traversal – 105. LeetCode

Constructing a binary tree from its preorder and inorder traversals involves rebuilding the tree using the order in which nodes are visited.

Preorder traversal visits the root node first, followed by the left and right subtrees, while inorder traversal visits the left subtree, root, and then the right subtree. By combining the two, we can uniquely reconstruct the binary tree. This is useful for problems where a tree’s structure needs to be determined from its traversal orders, such as restoring data or enabling traversal-based algorithms.

Understanding The Problem

You are provided with two integer arrays:

• preorder: The preorder traversal of a binary tree.

• inorder: The inorder traversal of the same binary tree.

Your goal is to reconstruct the binary tree from these traversal arrays and return the root node.

Before diving into the solution, let’s recall the traversal orders of a binary tree:

1. Preorder Traversal:

• The order is: Root → Left subtree → Right subtree.

• The first element of the preorder array is always the root of the tree.

2. Inorder Traversal:

• The order is: Left subtree → Root → Right subtree.

• In the inorder array, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree.

Example

Let’s take an example to understand how the tree is constructed:

Input:

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

Output (Binary Tree):

    3
   / \
  9   20
     /  \
    15   7

Key Insights to Solve the Problem

To reconstruct the binary tree, we need to leverage the following insights:

1. Preorder Identifies the Root

In preorder traversal, the first element is always the root. During the reconstruction process:

• The first element of the preorder array is the root of the entire tree.

• For each recursive step, the next element of the preorder array is the root of the current subtree.

For example:

Preorder: [3, 9, 20, 15, 7]

• Root of the tree: 3 (first element).

• Root of the left subtree: 9 (next in preorder after splitting).

• Root of the right subtree: 20.

2. Inorder Splits the Subtrees

In inorder traversal, the root splits the array into two parts:

• The elements to the left of the root in the inorder array form the left subtree.

• The elements to the right of the root form the right subtree.

Inorder: [9, 3, 15, 20, 7]

If 3 is the root (from preorder):

• Left subtree: [9]

• Right subtree: [15, 20, 7]

This clear boundary allows us to recursively construct the left and right subtrees.

3. The Perfect Complement

• Preorder gives you the hierarchy of the tree (roots in sequence).

• Inorder provides the relationships and structure (left and right boundaries).

Together, they resolve the ambiguity of tree structure that would arise if we used just one traversal.

Optimized Algorithm

We follow these steps:

1. Create a map of inorder values to their indices for fast lookups.

2. Start with the entire preorder and inorder arrays.

3. Recursively construct the tree:

• Pick the root from the preorder array.

• Find its position in the inorder array to determine the left and right subtrees.

• Recursively build the left and right subtrees.

4. Return the constructed tree.

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);
    }

    private TreeNode construct(int[] preorder, int preStart, int preEnd,
                               int[] inorder, int inStart, int inEnd,
                               Map<Integer, Integer> inorderMap) {
        if (preStart > preEnd || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int rootIndex = inorderMap.get(root.val);
        int leftTreeSize = rootIndex - inStart;

        root.left = construct(preorder, preStart + 1, preStart + leftTreeSize,
                              inorder, inStart, rootIndex - 1, inorderMap);
        root.right = construct(preorder, preStart + leftTreeSize + 1, preEnd,
                               inorder, rootIndex + 1, inEnd, inorderMap);

        return root;
    }
}

Step-by-Step Explanation

Step 1: Create an inorderMap

Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
    inorderMap.put(inorder[i], i);
}

• Avoids scanning the inorder array repeatedly, reducing the time complexity from O(n²) to O(n).