Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal arrays of a binary tree (with unique values), reconstruct the tree.

Function signature

func BuildTree(preorder []int, inorder []int) *TreeNode

Inputs / outputs

• preorder: root-left-right traversal.
• inorder: left-root-right traversal.
• Return: root of the reconstructed tree.

Example

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Output: root of the tree.

Constraints

• 0 <= len(preorder) == len(inorder) <= 100_000
• All values are unique.

Core idea (near-solution)

Preorder's first element is the root. In inorder, elements left of root belong to the left subtree, right of root to the right subtree. Use an index map for inorder positions.

Invariant: recursive calls are passed the correct slices (or indices) for each subtree.

Algorithm (step-by-step)

1. Build a map from value to inorder index.
2. Use a recursive helper with preorder index range and inorder index range.
3. Root = preorder[preL]. Find its index in inorder to split left/right sizes.
4. Recurse for left and right subtrees.

Correctness sketch

• Invariant: recursive calls are passed the correct slices (or indices) for each subtree.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

Trace (hand walkthrough)

Example input:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Output: root of the tree.

Walk:
- preorder[0]=3 -> root=3; inorder split: [9] | 3 | [15,20,7]
- left subtree from inorder [9] -> node 9
- right subtree: next preorder root=20; split inorder [15] |20| [7] -> children 15,7

Pitfalls to avoid

• Rebuilding sub-slices repeatedly (use indices).
• Not using a map for inorder indices (causes O(n^2)).

Complexity

• Time: O(n)
• Extra space: O(n) for the index map.

Implementation notes (Go)

• Build a value->index map for inorder to avoid O(n^2) scans.
• Use indices instead of slicing to reduce allocations.