Construct a Binary Tree from Preorder and Inorder Traversal

Building a unique binary tree given its Preorder and Inorder traversals is a foundational algorithmic problem in Data Structures and Algorithms (DSA). This chapter explores how traversal properties allow us to deterministically reconstruct the hierarchical structure of a tree, moving from a naive physical array-slicing mindset to an optimized pointer-based recursion model implemented in C++ and Java.

1. Why Do We Need This? (Problem Statement & Uniqueness)

When given random traversal sequences, a single traversal order (like only Preorder or only Postorder) is generally insufficient to uniquely determine a binary tree because multiple distinct tree topologies can yield the exact same traversal sequence.

However, pairing Preorder with Inorder (or Postorder with Inorder) provides enough constraint to guarantee a unique binary tree.

• Input: An inorder traversal array and a preorder traversal array of the same binary tree.
• Output: The root node of the constructed binary tree.
• Guarantee: The traversals of the reconstructed tree must match the original input traversals identically.

2. Core Mental Model & Traversal Properties

To solve this problem, we must exploit the structural definitions of both traversals:

• Preorder Traversal (Root, Left, Right): The very first element in any Preorder array is always the root of the current tree (or subtree).
• Inorder Traversal (Left, Root, Right): The root splits the array into two distinct halves: all elements to the left of the root belong to the left subtree, and all elements to the right belong to the right subtree.

Real-Life Analogy: The Corporate Hierarchy Blueprint

Imagine you are given two organizational charts for a company:

1. A Preorder list telling you who speaks first at every departmental meeting (which always starts with the department head).
2. An Inorder list telling you a strict seating arrangement from left to right across the auditorium.

By looking at who speaks first (Preorder head), you find that person in the seating chart (Inorder). Everyone seated to their immediate left belongs to their personal team (left subtree), and everyone seated to their right belongs to the external division (right subtree). You can recursively apply this rule down to every single employee until the entire organizational hierarchy is mapped out.

3. Visualizing the Subtree Breakdown

Let's examine how the arrays split during recursion. Suppose we have:

• Preorder: [10, 20, 40, 50, 30, 60]
• Inorder: [40, 20, 50, 10, 60, 30]

We have successfully divided the problem into two smaller sub-problems: constructing the left subtree with elements [40, 20, 50] and the right subtree with elements [60, 30].

4. Naive Approach vs. Optimized Pointer Strategy

The Naive Approach (Array Slicing)

A beginner might physically slice arrays (creating sub-arrays or vectors for every left and right recursive call).

• The Catch: Slicing arrays at every step consumes $O(N^2)$ or $O(N \log N)$ extra time and space due to memory allocation and copying, making it inefficient for production-scale trees.

The Optimized Pointer Strategy

Instead of physically copying arrays, we can track boundaries using four pointer indices:

1. preStart and preEnd: Boundaries for the active range in the Preorder array.
2. inStart and inEnd: Boundaries for the active range in the Inorder array.

5. Hashing for $O(1)$ Root Lookup

To find where the root element lies inside the Inorder array without scanning linearly (which takes $O(N)$ time per node), we store all Inorder element indices in a Hash Map beforehand.

6. Complete Flow Walkthrough

Here is the step-by-step recursive execution flow:

7. Production-Grade Code Implementation

Below are the clean, optimized C++ and Java implementations utilizing hash maps and boundary pointers.

C++ Implementation

#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
                              vector<int>& inorder, int inStart, int inEnd,
                              unordered_map<int, int>& inMap) {
        // Base case: if pointers cross, subtree is empty
        if (preStart > preEnd || inStart > inEnd) return nullptr;

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

        // Find the position of the root in the inorder traversal
        int inRoot = inMap[root->val];

        // Number of elements in the left subtree
        int numsLeft = inRoot - inStart;

        // Recursively build left and right subtrees using index bounds
        root->left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft,
                                     inorder, inStart, inRoot - 1, inMap);

        root->right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd,
                                      inorder, inRoot + 1, inEnd, inMap);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inMap;
        for (int i = 0; i < inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }

        return buildTreeHelper(preorder, 0, preorder.size() - 1,
                               inorder, 0, inorder.size() - 1, inMap);
    }
};

Java Implementation

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

        return buildTreeHelper(preorder, 0, preorder.length - 1, 
                               inorder, 0, inorder.length - 1, inMap);
    }

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
                                     int[] inorder, int inStart, int inEnd,
                                     Map<Integer, Integer> inMap) {
        // Base case
        if (preStart > preEnd || inStart > inEnd) return null;

        // Root creation
        TreeNode root = new TreeNode(preorder[preStart]);

        // Find root index in inorder array
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;

        // Recursive calls for left and right subtrees
        root.left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft,
                                    inorder, inStart, inRoot - 1, inMap);

        root.right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd,
                                     inorder, inRoot + 1, inEnd, inMap);

        return root;
    }
}

8. Complexity Analysis

Summary and Key Takeaways

• Uniqueness Guarantee: Combining an Inorder traversal with either a Preorder or Postorder traversal uniquely identifies any binary tree.
• Root Identification: The Preorder (or Postorder) traversal always reveals the root of the current subtree immediately (preorder[preStart]).
• Subtree Sizing: The Inorder traversal acts as the dividing wall, separating left subtree elements from right subtree elements relative to the root position.
• Avoid Array Slicing: Use index boundaries (preStart, preEnd, inStart, inEnd) to pass virtual sub-arrays without incurring memory reallocation overhead.
• Hash Map Optimization: Pre-indexing all inorder values into a hash map reduces root lookup time from $O(N)$ to $O(1)$.
• Recursive Paradigm: Tree reconstruction is fundamentally a divide-and-conquer problem solved cleanly via recursive DFS calls.