Construct Binary Tree from Preorder and Inorder Traversal

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

Why this is worth learning

Preorder chooses the next root; inorder tells which values belong to each child subtree. Unique values make the split unambiguous.

Before coding: one-minute experiment

For preorder [2,1,3] and inorder [1,2,3], which value is root and which inorder ranges belong to its children?

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 names a subtree's root first but does not say where that subtree ends. Inorder supplies the missing partition: everything before that root belongs left, and everything after it belongs right. Once the left size is known, the corresponding preorder slice has that many nodes after its root. A linear scan for the root at every level can repeat O(n²) work in a skewed tree; unique values let us build one value→inorder-position map. Explicit index ranges then assign each recursive call exactly the two intervals describing its subtree.

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

For an empty inorder interval, return nil. Otherwise the next unused preorder value is the root because preorder visits root before either child. Its unique inorder position partitions the interval into exactly the left-subtree values and right-subtree values. Consume the root and recursively build the left interval before the right, matching preorder's consumption order. By induction, both subtrees are reconstructed correctly; attaching them gives the unique tree with those traversals. The inorder index map makes every split constant-time expected, and each preorder value is consumed once.

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

• Copying traversal elements or repeatedly scanning inorder at each recursive call.
• Not using a map for inorder indices (causes O(n^2)).

Debugging lens

Use left chains, right chains, and irregular shapes. Verify both traversals and nil structure of the output. Keep traversal indices local to the call so repeated invocations do not share stale state.

Complexity

Expected time: O(n) using the inorder position map. Auxiliary storage: O(n) for the map plus O(h) recursion stack. Output storage: O(n) newly allocated nodes.

Implementation notes (Go)

• Build a value->index map for inorder to avoid O(n^2) scans.
• Go subslices share their backing array; taking a subslice does not copy its elements. The reference uses explicit inclusive ranges to make subtree ownership visible. The index map, rather than avoiding slice syntax, prevents O(n²) repeated searches.

Contract precision

The two traversals describe the same valid binary tree and have unique values. Invalid or inconsistent traversal pairs are outside this reconstruction contract.

Reconstruction checkpoint

Use preorder [14,8,5,11,20,17] and inorder [5,8,11,14,17,20]. Derive the root’s right-subtree ranges and its left child. What changes if values are no longer unique?

Return to Binary Tree General · Module quiz