Construct Binary Tree from Preorder and Inorder Traversal — Step-by-Step Visualization

Algorithm Pattern

Recursive Partitioning

Key Idea

Preorder traversal always starts with the root of the current subtree. Inorder traversal has the root in the middle, splitting it into a left subtree and a right subtree. We can recursively: (1) pick the first element of preorder as root, (2) find its position in inorder to determine left/right subtree boundaries, and (3) repeat for children.

Step-by-Step Approach

1. The first element in `preorder` is the current `root` node.
2. Find the index of this `root` in the `inorder` array. Let this be `mid`.
3. All elements to the left of `mid` in `inorder` belong to the left subtree.
4. All elements to the right of `mid` in `inorder` belong to the right subtree.
5. Recursively build the left and right subtrees by slicing the `preorder` and `inorder` arrays accordingly.

Common Gotchas

• Manual slicing of arrays is O(N^2). To optimize to O(N), use a hash map for inorder index lookups and pass index boundaries (left, right) instead of slicing.