Construct Tree from Preorder and Inorder Traversal

• Preorder visits node, left, right, so the first element is always the root of the current subtree.
• Inorder visits left, node, right, so the root's position splits the array into left and right subtree values.
• HashMap maps each value to its inorder index for O(1) root lookup.
• Preorder pointer moves forward, supplying each root in exactly the order needed.
• Build order requires left subtree first, then right, to match preorder's node-left-right sequence.
• Time is O(n) with the map; space is O(n) for the map and recursion.

What is the Construct Tree from Preorder and Inorder problem?

Given two arrays representing the preorder and inorder traversal of a binary tree with unique values, reconstruct and return the original tree. This problem tests understanding of how traversal orders encode tree structure and how to use that encoding to rebuild the tree.

package com.bank.service;

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

public class HierarchyRebuilder {
    private int preorderIndex = 0;
    private Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int inLeft, int inRight) {
        if (inLeft > inRight) return null;
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inorderMap.get(rootVal);
        root.left = build(preorder, inLeft, mid - 1);
        root.right = build(preorder, mid + 1, inRight);
        return root;
    }
}

Why does preorder plus inorder uniquely define a tree?

Preorder visits node-left-right, so the first element is always the root of the current subtree. Inorder visits left-node-right, so finding the root in the inorder array splits it into two halves: everything before the root belongs to the left subtree, and everything after belongs to the right subtree. This split is unambiguous when values are unique.

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

Root = 3 (first in preorder)
Inorder split: [9] | 3 | [15, 20, 7]
Left subtree values: [9]
Right subtree values: [15, 20, 7]

Next root from preorder: 9 (for left subtree)
Next root from preorder: 20 (for right subtree)

Why is the HashMap critical for performance?

Without the map, finding the root's position in the inorder array requires a linear scan, making the algorithm O(n^2) in the worst case. With the map, each lookup is O(1), and since each node is created exactly once, the total time is O(n).

// Without map: O(n) scan per node → O(n^2) total
for (int i = inLeft; i <= inRight; i++) {
    if (inorder[i] == rootVal) { mid = i; break; }
}

// With map: O(1) lookup per node → O(n) total
int mid = inorderMap.get(rootVal);

Why must you build left before right?

Preorder visits node, then left subtree, then right subtree. The preorder pointer moves forward as each root is consumed. If you build the right subtree first, it would consume values meant for the left subtree, corrupting the tree. The order must match the preorder traversal order.

// CORRECT: left first, then right
root.left = build(preorder, inLeft, mid - 1);   // consumes left's preorder values
root.right = build(preorder, mid + 1, inRight);  // consumes right's preorder values

// WRONG: right first, then left
root.right = build(preorder, mid + 1, inRight);  // steals left's values!
root.left = build(preorder, inLeft, mid - 1);    // gets wrong values

How does the base case work?

When inLeft > inRight, the inorder range is empty, meaning there are no nodes in this subtree. This is the signal to return null. It handles both empty subtrees and the leaf termination correctly.

if (inLeft > inRight) return null;

What about postorder and inorder reconstruction?

Postorder visits left, right, then node, so the last element is the root. You read postorder from right to left and must build the right subtree before the left to match the reverse order.

| Aspect | Preorder + Inorder | Postorder + Inorder |
|--------|-------------------|--------------------|
| Root location | First in preorder | Last in postorder |
| Pointer direction | Left to right | Right to left |
| Build order | Left then right | Right then left |

What are edge cases?

• Empty arrays: return null.
• Single element: return a leaf node.
• Skewed tree (all left or all right): one side of every split is always empty.
• The preorder and inorder arrays must represent the same tree; if they do not, the result is undefined.

// Edge case: single node
// Preorder: [1], Inorder: [1]
// Root = 1, no left or right subtree
// Result: a single leaf node with value 1

What are common mistakes?

The first mistake is forgetting to use a class-level preorder pointer and instead passing index ranges for both arrays, which complicates the logic. The second mistake is building right before left, which corrupts the preorder consumption order. The third mistake is searching linearly in the inorder array instead of using a map.

// WRONG: linear search without map
int mid = -1;
for (int i = inLeft; i <= inRight; i++) {
    if (inorder[i] == rootVal) { mid = i; break; }
}
// This works but is O(n^2) in the worst case

// CORRECT: use the precomputed map
int mid = inorderMap.get(rootVal);

What about duplicate values?

If the tree has duplicate values, the root's position in the inorder array is ambiguous because the same value appears multiple times. You cannot uniquely determine which occurrence is the root, so the tree cannot be uniquely reconstructed. The algorithm assumes unique values.

What should a senior engineer know?

At the National Bank of India, Rajesh used this to migrate an org hierarchy that a legacy system exported only as two separate traversal logs. The service rebuilt the actual tree from the preorder and inorder logs so it could be loaded into the new system. The HashMap kept the rebuild fast even for hierarchies with thousands of employees, and a validation step confirmed the rebuilt tree's traversals matched the originals.