Building Binary Trees from Traversals

1. The Key Insight: Combining Traversal Properties

Let's quickly recall the definitions of the traversals we'll be using:

• Preorder Traversal: Root -> Left -> Right
• Inorder Traversal: Left -> Root -> Right

The magic of this problem lies in combining the unique information each traversal provides:

1. The preorder traversal always gives you the root of any given tree or subtree. It's the very first element in the sequence.
2. The inorder traversal, once you know the root, tells you exactly which nodes belong to the left subtree and which belong to the right subtree. All elements to the left of the root in the inorder sequence form the left subtree, and all elements to the right form the right subtree.

Let's see this with an example. Suppose we have:

• preorder = [10, 20, 40, 50, 30, 60]
• inorder = [40, 20, 50, 10, 60, 30]

Let's apply the logic to our own example:

1. Find the Root: From the preorder array, the first element is 10. So, 10 is the root of our tree.
2. Split the Subtrees: Find 10 in the inorder array: [40, 20, 50, **10**, 60, 30].
   • Everything to the left of 10 ([40, 20, 50]) belongs to the left subtree.
   • Everything to the right of 10 ([60, 30]) belongs to the right subtree.

Now, we have two smaller, independent problems:

• Construct the left subtree using its inorder traversal [40, 20, 50] and its preorder traversal.
• Construct the right subtree using its inorder traversal [60, 30] and its preorder traversal.

This structure points directly to a recursive solution.

2. The Recursive Strategy

The core of the algorithm is a recursive function that builds a tree (or subtree) from the corresponding segments of the preorder and inorder arrays. To understand this strategy in detail, please watch the following video. It does an excellent job of visualizing how the main problem is broken down into subproblems.

As the video explains, the process for any given subtree is:

1. Pick the first element from the current preorder segment as the root.
2. Find this root element in the current inorder segment.
3. Count the number of elements in the left part of the inorder segment (numsLeft). These elements form the left subtree.
4. Recursively call the build function for the left subtree. The preorder segment for this call will be the next numsLeft elements from the current preorder segment. The inorder segment is the left part you identified.
5. Recursively call the build function for the right subtree. The preorder segment will be the remaining elements. The inorder segment is the right part you identified.
6. Connect the returned left and right subtrees to the root and return the root.

3. An Efficient Implementation in Java

A naive implementation might involve creating new sub-arrays for each recursive call. This is highly inefficient due to the overhead of array copying and would likely lead to a "Time Limit Exceeded" error in competitive programming platforms.

There are two key optimizations we must make, both of which are standard practice for interview-level problems:

1. O(1) Root Lookup: Instead of scanning the inorder array to find the root's index every time (an $O(N)$ operation), we can pre-process it. By storing the (value -> index) pairs of the inorder array in a HashMap, we can find any root's index in $O(1)$ time on average.
2. Pointer-based Array Segments: Instead of slicing arrays, we pass indices (pointers) that define the boundaries of the current preorder and inorder segments for each recursive call. This avoids creating new arrays and uses constant extra space per call.

The article below provides a concise summary of the algorithm and a clean Java implementation incorporating these optimizations.

Here is the Java code from the article for your reference. It's a template you should become very familiar with.

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Create a map for efficient lookup of inorder indices
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }

        // Start the recursive construction
        TreeNode root = build(preorder, 0, preorder.length - 1,
                              inorder, 0, inorder.length - 1, inMap);
        
        return root;
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd,
                           int[] inorder, int inStart, int inEnd, 
                           Map<Integer, Integer> inMap) {
        
        // Base case: If the pointers cross, it means the segment is empty.
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // The first element in the preorder segment is the root.
        TreeNode root = new TreeNode(preorder[preStart]);

        // Find the root's index in the inorder segment.
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart; // Number of nodes in the left subtree.

        // Recursively build the left subtree.
        // Preorder for left: starts right after the root, and includes 'numsLeft' elements.
        // Inorder for left: starts at 'inStart' and ends just before 'inRoot'.
        root.left = build(preorder, preStart + 1, preStart + numsLeft,
                          inorder, inStart, inRoot - 1, inMap);
        
        // Recursively build the right subtree.
        // Preorder for right: starts after the elements of the left subtree.
        // Inorder for right: starts just after 'inRoot'.
        root.right = build(preorder, preStart + numsLeft + 1, preEnd,
                           inorder, inRoot + 1, inEnd, inMap);

        return root;
    }
}

Complexity Analysis

• Time Complexity: $O(N)$, where N is the number of nodes. Building the HashMap takes $O(N)$ time, and the recursive build function visits each node exactly once.
• Space Complexity: $O(N)$. In the worst case of a skewed tree, the recursion depth will be $N$, leading to $O(N)$ space on the call stack. The HashMap also requires $O(N)$ space. For a balanced tree, the recursion stack space would be $O(\log N)$.

Conclusion

Congratulations! You've learned how to solve a fundamental and frequently asked tree problem. This exercise beautifully combines your knowledge of traversals, recursion, and data structures like HashMaps to create an elegant and efficient solution.

Key Takeaways:

• A binary tree can be uniquely constructed from its preorder and inorder traversals.
• The preorder traversal identifies the root of any subtree.
• The inorder traversal splits the nodes into left and right subtrees relative to the root.
• A recursive approach is the natural way to solve this problem by breaking it down into smaller subproblems.
• For an efficient solution, use a HashMap for O(1) index lookups and index pointers to avoid creating new sub-arrays.

Preview of the Next Lesson:
In the next lesson, we'll tackle a very similar problem: constructing a binary tree from its postorder and inorder traversals. The core logic will be almost identical, but with one crucial difference. Think about where the root appears in a postorder traversal—that's the key to adapting today's algorithm