Construct Binary Tree from Preorder and Inorder

Problem Statement

Given two integer arrays preorder and inorder where:

• preorder is the preorder traversal of a binary tree
• inorder is the inorder traversal of the same tree

Construct and return the binary tree.

Examples

Example 1

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

Tree:
      3
     / \
    9  20
      /  \
     15   7

Example 2

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

Intuition

Key Observations:

1. Preorder: root → left → right (first element is always root)
2. Inorder: left → root → right (root splits left and right subtrees)

Algorithm:

1. First element of preorder is the root
2. Find root in inorder → this splits inorder into left and right subtrees
3. Elements to left of root in inorder = left subtree
4. Elements to right of root in inorder = right subtree
5. Recursively build left and right subtrees

Example:

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

Step 1: Root = 3 (first in preorder)
Step 2: Find 3 in inorder → splits at index 1
        left_inorder = [9]
        right_inorder = [15, 20, 7]
Step 3: Split preorder accordingly:
        left_preorder = [9]      (next 1 element)
        right_preorder = [20, 15, 7]  (remaining)
Step 4: Recursively build subtrees

Pattern Recognition

This is a Divide and Conquer + Tree Construction problem:

• Use preorder to identify roots
• Use inorder to partition subtrees
• Recursive structure

Approach

Recursive with Index Map

1. Preprocess: Create hashmap of value → index in inorder (O(1) lookup)

2. Recursive Function: build(pre_start, pre_end, in_start, in_end)

   • Base case: if start > end, return null
   • Root = preorder[pre_start]
   • Find root_index in inorder using hashmap
   • Calculate left_subtree_size = root_index - in_start
   • Build left subtree with appropriate ranges
   • Build right subtree with appropriate ranges
   • Return root

3. Initial Call: build(0, n-1, 0, n-1)

Time Optimization: HashMap for O(1) lookup instead of O(n) search.

Edge Cases

• Single node
• Skewed tree (all left or all right)
• Duplicate values (problem states values are unique)
• Empty arrays

Complexity Analysis

• Time: O(n) where n = number of nodes

  • Build hashmap: O(n)
  • Visit each node once: O(n)
  • O(1) lookup per node with hashmap

• Space: O(n)

  • Hashmap: O(n)
  • Recursion stack: O(h) = O(log n) to O(n)
  • Total: O(n)