Construct Binary Tree from Preorder and Inorder Traversal

Problem

You are given two integer arrays that describe the same binary tree: preorder, the sequence of values visited by a preorder traversal (node, then left subtree, then right subtree), and inorder, the sequence visited by an inorder traversal (left subtree, node, right subtree). All values are distinct. Rebuild the tree and return its root.

• Both arrays have the same length, between 1 and 8,000.
• Values are distinct integers (negative values allowed).
• The two arrays contain the same set of values and describe one valid tree.

Examples

• preorder = [6, 2, 1, 4, 9, 12], inorder = [1, 2, 4, 6, 9, 12] → [6, 2, 9, 1, 4, None, 12]. The root is 6; in inorder the [1, 2, 4] to its left is the whole left subtree and [9, 12] is the right subtree.
• preorder = [5], inorder = [5] → [5].
• preorder = [4, 7, 10], inorder = [10, 7, 4] → [4, 7, None, 10]. A left-leaning chain: each root is the last element of its inorder slice.

Hints

1. What does the first element of preorder tell you? Where does that value appear in inorder, and what does its position split?
2. Once you know the left subtree has L nodes, which slice of preorder describes it?
3. Recurse on index ranges rather than copying subarrays, and precompute a value-to-index map for inorder so each split is O(1).