LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

The problem is asking us to reconstruct a binary tree given two traversal orders: preorder and inorder. In a preorder traversal, nodes are visited in the order: root, left subtree, right subtree.

leetcodemediumarrayhash-tabledivide-and-conquertreebinary-tree

LeetCode Problem 105

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Solution

Problem Understanding

The problem is asking us to reconstruct a binary tree given two traversal orders: preorder and inorder. In a preorder traversal, nodes are visited in the order: root, left subtree, right subtree. In an inorder traversal, nodes are visited in the order: left subtree, root, right subtree.

Given these two sequences, the task is to rebuild the exact original tree structure and return its root. Each value in the arrays is unique, which guarantees that each node can be uniquely identified in the traversals. The constraints indicate that the arrays can be as large as 3000 elements, so any approach must handle moderately large input efficiently.

Edge cases include the smallest trees (single node), completely left- or right-skewed trees, and empty inputs (though the constraints guarantee at least one node). The uniqueness guarantee simplifies the problem because we do not have to handle duplicate values.

Approaches

The brute-force approach would be to iterate through the preorder array, treating each element as a potential root, and recursively try all possible splits in the inorder array to build left and right subtrees. While this approach would work logically, it is inefficient because it repeatedly searches for root indices in the inorder array, giving O(n^2) time complexity.

The optimal approach relies on two key observations. First, the first element of preorder is always the root. Second, the index of this root in the inorder array partitions the array into left and right subtrees. Using a hash map to store the indices of values in the inorder array allows O(1) lookup for the root position, making recursive construction efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Searches for root index in inorder in each recursion
Optimal O(n) O(n) Uses hash map for root indices, recursive construction

Algorithm Walkthrough

  1. Construct a hash map from inorder values to their indices. This allows O(1) access to the position of any root in inorder.
  2. Maintain a pointer or index in preorder to know which node is the current root. Start at 0.
  3. Define a recursive function build_subtree(left, right) where left and right are the boundaries of the current subtree in the inorder array.
  4. Base case: if left > right, return None because there are no nodes to process.
  5. Take the current root value from preorder[current_index] and increment the index.
  6. Create a new tree node with this root value.
  7. Recursively construct the left subtree using the indices left to root_index_in_inorder - 1.
  8. Recursively construct the right subtree using the indices root_index_in_inorder + 1 to right.
  9. Return the root node after both subtrees are attached.

Why it works: At each step, we ensure the node from preorder is placed at the correct position determined by its inorder index. The recursion guarantees that all nodes are placed correctly relative to their parent, preserving the original tree structure.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> 'Optional[TreeNode]':
        if not preorder or not inorder:
            return None
        
        # Map each value to its index in inorder
        inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
        preorder_index = 0
        
        def build_subtree(left: int, right: int) -> 'Optional[TreeNode]':
            nonlocal preorder_index
            if left > right:
                return None
            
            root_val = preorder[preorder_index]
            preorder_index += 1
            root = TreeNode(root_val)
            
            root.left = build_subtree(left, inorder_index_map[root_val] - 1)
            root.right = build_subtree(inorder_index_map[root_val] + 1, right)
            
            return root
        
        return build_subtree(0, len(inorder) - 1)

The Python implementation first constructs a hash map to map values to indices in inorder. We maintain a preorder_index to know which node to process next. The recursive build_subtree function ensures that for each root, its left and right subtrees are correctly built using the inorder boundaries.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }
    
    inorderIndexMap := make(map[int]int)
    for i, val := range inorder {
        inorderIndexMap[val] = i
    }
    
    preorderIndex := 0
    
    var buildSubtree func(left, right int) *TreeNode
    buildSubtree = func(left, right int) *TreeNode {
        if left > right {
            return nil
        }
        
        rootVal := preorder[preorderIndex]
        preorderIndex++
        root := &TreeNode{Val: rootVal}
        
        root.Left = buildSubtree(left, inorderIndexMap[rootVal]-1)
        root.Right = buildSubtree(inorderIndexMap[rootVal]+1, right)
        
        return root
    }
    
    return buildSubtree(0, len(inorder)-1)
}

In Go, we handle recursion similarly but need to explicitly manage pointers to TreeNode. The preorderIndex variable is kept in the closure of buildSubtree. Nil pointers are used instead of Python’s None.

Worked Examples

Example 1: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Step preorder_index root_val left subtree indices right subtree indices Notes
1 0 3 0-0 2-4 Root is 3
2 1 9 0--1 N/A Left child 9 (no left/right)
3 2 20 2-2 4-4 Right child 20
4 3 15 2-1 N/A Left child 15 (no children)
5 4 7 4-3 N/A Right child 7 (no children)

Example 2: preorder = [-1], inorder = [-1]

Only one node, root = -1, no left or right children.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is processed exactly once. Hash map lookup is O(1).
Space O(n) Hash map uses O(n), recursion stack can go up to O(n) in skewed tree.

The algorithm is efficient because we avoid repeated scanning of the inorder array using the hash map, and recursion ensures we only build each node once.

Test Cases

# Provided examples
assert Solution().buildTree([3,9,20,15,7], [9,3,15,20,7]).val == 3  # standard case
assert Solution().buildTree([-1], [-1]).val == -1  # single node

# Edge cases
assert Solution().buildTree([1,2], [2,1]).val == 1  # left-skewed
assert Solution().buildTree([1,2], [1,2]).val == 1  # right-skewed
assert Solution().buildTree([1,2,3], [2,1,3]).val == 1  # root with two children
Test Why
[3,9,20,15,7] Standard tree reconstruction
[-1] Single node edge case
[1,2], [2,1] Left-skewed tree
[1,2], [1,2] Right-skewed tree
[1,2,3], [2,1,3] Root with two children

Edge Cases

Single Node Tree: When preorder and inorder have one element, the tree has only a root. Implementation handles this because the base case in recursion returns the node correctly.

Skewed Trees: Fully left- or right-skewed trees could reach recursion depth equal to the number of nodes. The algorithm handles this, and Python/Go recursion depth limits are sufficient for n ≤ 3000.

Empty Input: Constraints guarantee at least one node, but code defensively handles empty lists by returning None or nil. This prevents potential index errors during recursive calls.