Construct Binary Tree from Preorder and Inorder

Medium

The problem

You get two lists describing the same binary tree: preorder (node, then left subtree, then right subtree) and inorder (left subtree, then node, then right subtree). Rebuild the tree and return its root.

Example 1
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
Preorder starts with the root 3. In inorder, 9 is left of 3 and 15, 20, 7 are right of it.
Example 2
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Limits

1 ≤ number of nodes ≤ 3,000
All values are different
The two lists always describe one valid tree

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The first preorder value is always the root. Where does that value sit in inorder, and what does it split?

The idea

Root = preorder[0]; find its index in inorder (use a map) → size of the left subtree; recurse on the matching slices.

Target: O(n) time with an index map

Go function shape

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

Reference solution

Tested with go test. Try it yourself first, then compare.

// BuildTree: preorder[0] is the root. Its position in inorder splits the other values into the left and
// right subtrees, and the left subtree's size tells you where its preorder values end.
func BuildTree(preorder, inorder []int) *TreeNode {
	pos := make(map[int]int, len(inorder)) // value -> index in inorder
	for i, v := range inorder {
		pos[v] = i
	}
	next := 0                            // next unused index of preorder
	var build func(lo, hi int) *TreeNode // builds the subtree covering inorder[lo..hi]
	build = func(lo, hi int) *TreeNode {
		if lo > hi {
			return nil
		}
		root := &TreeNode{Val: preorder[next]}
		next++
		mid := pos[root.Val]
		root.Left = build(lo, mid-1) // preorder visits the whole left subtree before the right one
		root.Right = build(mid+1, hi)
		return root
	}
	return build(0, len(inorder)-1)
}

Read the lesson: Trees: BFS / DFS