Building a Binary Tree from Traversals

Lesson Recap and Today's Goal

Let's quickly recap the key insight from our last session:

• Preorder (Root -> Left -> Right) gives you the root of any subtree (it's the first element).
• Inorder (Left -> Root -> Right) partitions the nodes into left and right subtrees once the root is known.

Today's problem swaps preorder for postorder. Our goal is to adapt our previous algorithm to work with this new combination. By the end of this lesson, you will be able to:

• Explain how to identify the root and partition subtrees using postorder and inorder traversals.
• Adapt the recursive algorithm to build the tree from these traversals.
• Implement an efficient, interview-ready solution in Java.

1. The Core Logic: Finding the Root in Postorder

The fundamental properties of the traversals are our guide:

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

The main difference is immediately apparent: in a postorder sequence, the root of any tree or subtree is always the last element.

This is our new starting point. The role of the inorder traversal remains unchanged: it helps us divide the nodes into left and right subtrees.

Let's use an example:

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

1. Find the Root: The last element of the postorder array is 10. This is the root of the entire tree.

2. Partition 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. There are 3 nodes.
   • Everything to the right of 10 ([60, 30]) belongs to the right subtree. There are 2 nodes.

3. Find the Traversal for Subtrees: This is the trickiest part. We know the number of nodes in each subtree. We can use this information to partition the postorder array.

   • The postorder traversal is Left -> Right -> Root.
   • The left subtree has 3 nodes, so the first 3 elements of our postorder array ([40, 50, 20]) must be the postorder traversal for the left subtree.
   • The right subtree has 2 nodes, so the next 2 elements ([60, 30]) must be the postorder traversal for the right subtree.
   • The final element (10) is the root we've already used.

This process gives us two independent subproblems, which points directly to a recursive solution, just like before.

2. The Recursive Strategy and Implementation

To see a detailed walkthrough of this recursive logic, the following video is an excellent resource. It builds directly on the concepts from the preorder/inorder problem.

As with the previous problem, a naive implementation that creates new subarrays in each recursive call is too slow. We will use the same optimizations for an efficient, $O(N)$ solution:

1. HashMap for Inorder Indices: Pre-process the inorder array into a HashMap to find the index of any root in $O(1)$ average time.
2. Index Pointers: Use start and end indices to define the array segments for each recursive call, avoiding any array copying.

The following article provides a concise summary and a clean, optimized Java implementation.

Here is the essential Java code from the article. It should look very familiar, but with key differences in the build function.

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

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length) {
            return null;
        }

        // Pre-process inorder array for O(1) lookups
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }

        return build(inorder, 0, inorder.length - 1,
                     postorder, 0, postorder.length - 1, inMap);
    }

    private TreeNode build(int[] inorder, int inStart, int inEnd,
                           int[] postorder, int postStart, int postEnd,
                           Map<Integer, Integer> inMap) {
        
        // Base case: segment is empty
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        // The LAST element in the postorder segment is the root
        TreeNode root = new TreeNode(postorder[postEnd]);

        // Find 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
        // Inorder for left: [inStart, inRoot - 1]
        // Postorder for left: [postStart, postStart + numsLeft - 1]
        root.left = build(inorder, inStart, inRoot - 1,
                          postorder, postStart, postStart + numsLeft - 1, inMap);
        
        // Recursively build the right subtree
        // Inorder for right: [inRoot + 1, inEnd]
        // Postorder for right: [postStart + numsLeft, postEnd - 1]
        root.right = build(inorder, inRoot + 1, inEnd,
                           postorder, postStart + numsLeft, postEnd - 1, inMap);

        return root;
    }
}

A Note on Implementation Strategy

In the code above, the recursive calls for root.left and root.right are made in that order. An alternative, equally valid approach involves processing the postorder array backwards with a single global index pointer. In that case, you would build the right subtree first, then the left, to match the Right -> Left -> Root order of processing. Both strategies are correct, but the one shown here is more directly analogous to the preorder/inorder algorithm we already learned.

Conclusion

Excellent work! You have now mastered the two most common variations of the tree construction problem. Recognizing the pattern—identifying the root from one traversal and partitioning with inorder—is the key to solving these questions efficiently in an interview setting.

Key Takeaways:

• A binary tree can be uniquely constructed from its postorder and inorder traversals.
• The postorder traversal identifies the root of any subtree as its last element.
• The inorder traversal's role of partitioning the tree into left and right subtrees remains the same.
• The efficient $O(N)$ solution uses a HashMap and index pointers, just like the preorder/inorder version.

This lesson concludes our module on general binary trees. You have built a strong foundation in traversals, analysis, and construction.

Preview of the Next Module:
We are now ready to move on to a special, highly structured type of tree: the Binary Search Tree (BST). BSTs impose a specific ordering on their nodes, which enables highly efficient searching, insertion, and deletion operations. In our next lesson, we will start by implementing a BST and its core operations from scratch.