Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium
Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree
Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Problem Description

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:


Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Solution

1. Problem Deconstruction

Technical Definition:
Given two integer arrays preorder (root → left subtree → right subtree) and inorder (left subtree → root → right subtree) representing traversals of a binary tree with unique values, reconstruct the original binary tree. The solution must map each subtree root from preorder to its position in inorder to recursively partition both arrays into left/right subtrees.

Beginner Explanation:
Imagine you have two lists of the same tree’s node values:

List 1 (preorder): First value is the tree’s root, followed by all values from the left branch, then the right branch.
List 2 (inorder): Values from the left branch first, then the root, then the right branch.
Your task is to rebuild the tree by repeatedly:

Picking the next root from List 1,
Finding it in List 2 to split into left/right sections,
Using the section sizes to split List 1 accordingly.

Mathematical Formulation:
Let:

$P = [p_0, p_1, \ldots, p_{n-1}]$ be the preorder sequence.
$I = [i_0, i_1, \ldots, i_{n-1}]$ be the inorder sequence.
Define:
$r = P[0]$ (root value).
$k$ such that $I[k] = r$ .
Then:
Left subtree:
- Preorder: $P[1 : k+1]$
- Inorder: $I[0 : k]$
Right subtree:
- Preorder: $P[k+1 : n]$
- Inorder: $I[k+1 : n]$
  Recurse until sequences are empty.

Constraint Analysis:

Lengths 1–3000:
- Limits maximum recursion depth to 3000 (safe in most languages).
- Rules out O(n³) solutions but allows O(n²) brute-force.
Unique values:
- Enables hashmap use for O(1) inorder lookups.
- Eliminates ambiguity in subtree partitioning.
Matching values:
- Guarantees a valid solution exists.
Preorder/inorder validity:
- Ensures input consistency (no need for validation).
  Edge Cases:

Single-node tree: Handled by base case (arrays of length 1).
Skewed trees (e.g., all left children): Recursion depth = n (handled by stack).
Root at inorder start/end: One subtree is empty.

2. Intuition Scaffolding

Real-World Metaphor:
Rebuilding a furniture assembly from two instruction sheets:

Preorder: Step-by-step assembly order (start with base, attach left leg, then right leg).
Inorder: Disassembly labels grouped by component (left leg parts, base, right leg parts).
Match components by cross-referencing sheets.

Gaming Analogy:
In a skill-tree game:

Preorder: Order you unlock skills (root skill first).
Inorder: Prerequisite groupings (left-branch skills before root).
Reconstruct the tree by aligning unlock order with prerequisites.

Math Analogy:
Solving a recurrence relation:

Root = initial condition.
Partitioning arrays = breaking into subproblems.
Hashmap = memoization for constant-time lookups.

Common Pitfalls:

Global min/max fallacy: Assuming the first/last inorder value is the root (root comes from preorder).
Index miscalculation: Incorrectly splitting preorder (e.g., not accounting for root consumption).
Recursion without base case: Causing stack overflow for empty subtrees.
O(n²) search per node: Scanning inorder linearly for each root (use hashmap instead).
Array copying: Slicing arrays repeatedly wastes O(n²) time/space.

3. Approach Encyclopedia

Brute-Force (Recursive with Linear Search)

Pseudocode:

def buildTree(preorder, inorder):  
    if not preorder: return None  
    root_val = preorder[0]  
    root = TreeNode(root_val)  
    # Find root in inorder (O(n) per node)  
    in_index = inorder.index(root_val)  
    # Split arrays (O(n) slicing)  
    root.left = buildTree(preorder[1:1+in_index], inorder[:in_index])  
    root.right = buildTree(preorder[1+in_index:], inorder[in_index+1:])  
    return root

Complexity Proof:

Time: $T(n) = O(n) + T(k) + T(n-k-1)$ . Worst-case $O(n^2)$ (skewed tree).
Space: $O(n^2)$ (slicing creates $O(n)$ copies per level).

Visualization:

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]  
Root: 3 (from preorder[0])  
Find 3 in inorder → index=1  
Left:  
  preorder: [9] (indices 1:1+1)  
  inorder: [9] (indices 0:1)  
Right:  
  preorder: [20,15,7] (indices 2:5)  
  inorder: [15,20,7] (indices 2:5)

Optimal (Recursive with Hashmap and Pointers)

Pseudocode:

def buildTree(preorder, inorder):  
    index_map = {val: idx for idx, val in enumerate(inorder)}  
    return build(0, len(preorder)-1, 0, len(inorder)-1, index_map)  

def build(pre_start, pre_end, in_start, in_end, index_map):  
    if pre_start > pre_end: return None  
    root_val = preorder[pre_start]  # Current root  
    root = TreeNode(root_val)  
    in_root = index_map[root_val]  # O(1) lookup  
    left_size = in_root - in_start  # Nodes in left subtree  
    # Partition preorder:  
    #   Left: [pre_start+1, pre_start+left_size]  
    #   Right: [pre_start+left_size+1, pre_end]  
    root.left = build(pre_start+1, pre_start+left_size, in_start, in_root-1, index_map)  
    root.right = build(pre_start+left_size+1, pre_end, in_root+1, in_end, index_map)  
    return root

Complexity Proof:

Time: $O(n)$ (each node processed once, hashmap built in $O(n)$ ).
Space: $O(n)$ (hashmap $O(n)$ , recursion depth $O(n)$ worst-case).

Visualization:

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]  
Hashmap: {9:0, 3:1, 15:2, 20:3, 7:4}  
Root: preorder[0]=3 → index_map[3]=1  
Left subtree size = 1 - 0 = 1  
Left:  
  preorder: indices [1,1] (9)  
  inorder: indices [0,0] (9)  
Right:  
  preorder: indices [2,4] (20,15,7)  
  inorder: indices [2,4] (15,20,7)

4. Code Deep Dive

Optimal Solution (Python):

class Solution:  
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:  
        # Map: value → inorder index  
        index_map = {val: idx for idx, val in enumerate(inorder)}  
        # Recurse using array indices  
        return self.build(0, len(preorder)-1, 0, len(inorder)-1, preorder, index_map)  
      
    def build(self, pre_start: int, pre_end: int, in_start: int, in_end: int, preorder: List[int], index_map: dict) -> TreeNode:  
        # Base case: empty subtree  
        if pre_start > pre_end:  
            return None  
        # Root is first in preorder segment  
        root_val = preorder[pre_start]  
        root = TreeNode(root_val)  
        # Find root position in inorder  
        in_root = index_map[root_val]  
        # Size of left subtree  
        left_size = in_root - in_start  
        # Recurse left:  
        #   Preorder: after root (pre_start+1) for left_size elements  
        #   Inorder: left of root (in_start to in_root-1)  
        root.left = self.build(  
            pre_start + 1,  
            pre_start + left_size,  
            in_start,  
            in_root - 1,  
            preorder,  
            index_map  
        )  
        # Recurse right:  
        #   Preorder: after left subtree (pre_start+left_size+1 to pre_end)  
        #   Inorder: right of root (in_root+1 to in_end)  
        root.right = self.build(  
            pre_start + left_size + 1,  
            pre_end,  
            in_root + 1,  
            in_end,  
            preorder,  
            index_map  
        )  
        return root

Line-by-Line Analysis:

index_map construction: O(n) time to map inorder values to indices.
build parameters: Track current segments via start/end indices (avoids array slicing).
Base case (pre_start > pre_end): Handles empty subtrees (e.g., leaf nodes).
in_root = index_map[root_val]: O(1) lookup for root position in inorder.
left_size = in_root - in_start: Computes left subtree node count.
Left recursion:
- pre_start+1: Skip root in preorder.
- pre_start+left_size: End of left subtree in preorder.
- in_start to in_root-1: Left subtree in inorder.
Right recursion:
- pre_start+left_size+1: Start after left subtree.
- in_root+1 to in_end: Right subtree in inorder.

Edge Case Handling:

Example 1: Works as visualized above.
Example 2 (single node):
- pre_start=0, pre_end=0 → root created.
- left_size = index_map[-1] - 0 = 0 → left/right recursions have pre_start > pre_end → return None.
Left-skewed tree (e.g., preorder=[1,2,3], inorder=[3,2,1]):
- Root=1, in_root=2, left_size=2 → left recursion: preorder[1:3]=[2,3], inorder[0:1]=[3,2].

5. Complexity War Room

Hardware-Aware Analysis:

3000 nodes:
- Recursion depth: 3000 (stack safe in Python/Java).
- Hashmap: 3000 entries × 24 bytes ≈ 72KB (fits in CPU cache).
Time: O(n) → 3000 operations (negligible).

Industry Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute-force	O(n²)	O(n²)	9/10	❌ Fails large n
Optimal (hashmap)	O(n)	O(n)	8/10	✅ Preferred
Iterative stack	O(n)	O(n)	6/10	⚠️ Less intuitive

6. Pro Mode Extras

Variants:

Two transactions (LC 123): Extend to track buy/sell states.
k transactions (LC 188): Use DP with O(nk) time.
Construct from postorder+inorder: Root at end of postorder.
Serialize/deserialize (LC 297): Encode traversal orders.

Interview Cheat Sheet:

First mention: “O(n) time with O(n) space using hashmap for inorder lookups.”
Key insight: “Preorder defines roots, inorder defines subtree boundaries.”
Test verbally: Single-node, left-skewed, right-skewed cases.
Optimization path: “Brute-force → hashmap → iterative (if time).”

#105 - Construct Binary Tree from Preorder and Inorder Traversal