Start learning free

LESSON 421 OF 540 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in Go: O(n) with a Map

Practice O(n) Read the full explanation

Two arrays describe the same binary tree:

preorder lists the values in preorder: first a node, then its whole left subtree, then its whole right subtree.
inorder lists the values in inorder: first a node's whole left subtree, then the node, then its whole right subtree.

All the values are different. Build the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
    3
   / \
  9   20
     /  \
    15   7

Explanation: preorder starts with 3, so 3 is the root. In inorder, 9 is left of 3 and 15, 20, 7 are right of it: 9 is the left subtree and 15, 20, 7 are the right subtree. The right subtree's values come next in preorder, starting with 20, its root; in inorder 15 is left of 20 and 7 is right of it.

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single value is a tree with only a root.

Example 3:

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
      1
     /
    2
   /
  3

Explanation: In inorder, every value comes before its parent, so each node has only a left child. The same preorder with inorder = [1,2,3] would give a line going right: [1,null,2,null,3].

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
Every value is between -3000 and 3000, and the values are all different.
preorder and inorder are the preorder and inorder traversals of the same tree.
The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of values: build each node once, and find where a value sits in inorder with a map instead of a search.

STEP 1 OF 13

Guided

Ctrl + Enter to check

GO · BINARY TREES

Construct Binary Tree From Preorder And Inorder Traversal in Go, explained

Problem overview

The function buildTree receives two slices, preorder and inorder, which list the values of the same binary tree in two different orders. All values are different. The function builds the tree and returns its root, a *TreeNode. The lesson provides the TreeNode struct, with the fields Val, Left and Right.

Preorder lists a node first, then its whole left subtree, then its whole right subtree.
Inorder lists a node's whole left subtree first, then the node, then its whole right subtree.

In the first example, preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7]. The result, printed level by level with null for missing children, is [3,9,20,null,null,15,7]: the root 3 has the left child 9 and the right child 20, and 20 has the children 15 and 7.

Approach: preorder gives roots, inorder gives the split

Neither list is enough alone, but together they pin the tree down.

The first value of preorder is the root of the whole tree.
In inorder, the root sits between its two subtrees: everything to its left is the left subtree and everything to its right is the right subtree.

With preorder = [3,9,20,15,7], the root is 3. In inorder = [9,3,15,20,7] the value 3 is at index 1, so 9 forms the left subtree and 15, 20, 7 form the right one. The same idea applies to each subtree. Preorder visits the left subtree completely before the right one, so reading preorder from left to right hands out the roots in exactly the order the recursion needs them: this subtree's root, then the roots of its left subtree, then those of its right subtree.

The only costly part is finding where a value sits in inorder. Scanning the slice each time would make the whole solution O(n²) on a tree that is a long chain. The statement asks for O(n), so the solution builds a map from each value to its index once. This works because the values are all different: each value has exactly one index.

Step by step

Create the map. inorderIndex starts as an empty map[int]int, declared with :=.
Loop over inorder with range, which gives each index i and its value.
Store each pair: inorderIndex[value] = i. Afterwards, a lookup answers "where does this value sit?" in constant time.
Start the counter. preIndex := 0 is the position in preorder of the next root to use.
Call the helper build for the whole range of inorder, from 0 to len(inorder)-1. The call passes &preIndex, the address of the counter, so that every recursive call advances the same counter.
Declare the helper. It takes preorder, the map, the pointer preIndex *int and lo, hi int, the first and last index of the part of inorder that holds this subtree's values. It returns the subtree's root.
Stop on an empty range. If lo > hi, there are no values, so return nil. This is where the recursion ends, below the leaves.
Take the next root from preorder[*preIndex], then move the counter with *preIndex++.
Create the node with &TreeNode{Val: value}.
Find the split with mid := inorderIndex[value]. The indexes from lo to mid - 1 belong to the left subtree and those from mid + 1 to hi to the right one.
Build the left subtree first, from lo to mid - 1. Its roots come right after this node in preorder.
Then build the right subtree, from mid + 1 to hi. By now the left subtree has used up all its roots, so the counter points at the right subtree's root.
Return the node.

For the first example, the calls of build run in this order, where lo and hi are indexes into inorder:

build lo=0 hi=4  root 3, mid 1
build lo=0 hi=0  root 9, mid 0
  (two empty ranges: lo=0 hi=-1, then lo=1 hi=0)
build lo=2 hi=4  root 20, mid 3
build lo=2 hi=2  root 15, mid 2
  (two empty ranges)
build lo=4 hi=4  root 7, mid 4
  (two empty ranges)

The roots 3, 9, 20, 15, 7 appear in exactly the order of preorder.

The solution in Go

func buildTree(preorder []int, inorder []int) *TreeNode {
	inorderIndex := map[int]int{}
	for i, value := range inorder {
		inorderIndex[value] = i
	}
	preIndex := 0
	return build(preorder, inorderIndex, &preIndex, 0, len(inorder)-1)
}

func build(preorder []int, inorderIndex map[int]int, preIndex *int, lo, hi int) *TreeNode {
	if lo > hi {
		return nil
	}
	value := preorder[*preIndex]
	*preIndex++
	node := &TreeNode{Val: value}
	mid := inorderIndex[value]
	node.Left = build(preorder, inorderIndex, preIndex, lo, mid-1)
	node.Right = build(preorder, inorderIndex, preIndex, mid+1, hi)
	return node
}

The Go details worth knowing:

Why a pointer to the counter. Go passes an int by value, so a plain preIndex int parameter would be a copy, and a change inside one call would be invisible to the caller. Passing &preIndex gives every call the same variable. *preIndex reads or writes the value it points to.
*preIndex++ in one line. In Go, ++ is a statement, not an expression, and it applies to *preIndex, the value behind the pointer. That is why it sits on its own line after the read.
The order of reading and moving matters. value := preorder[*preIndex] comes before the increment, so the node gets the current root and the counter moves to the next one.
Map and slice parameters. A map is a reference to shared data, so passing inorderIndex does not copy it. A slice header is copied, but it points to the same elements. Neither preorder nor the map is changed after construction.
&TreeNode{Val: value}. This builds a struct and returns its address. Left and Right start as nil, their zero value, until the recursive calls set them.
lo, hi int. Consecutive parameters of the same type can share one type name.
The order of the two recursive calls is not cosmetic. They are two statements that run one after the other, and the first one moves the shared counter.

Complexity

Time: O(n). Filling the map visits each value once. Each call of build that gets past the empty-range check creates exactly one node and does a constant amount of work, including the map lookup, and there are n such calls. The calls that return nil number at most n + 1.

Space: O(n). The map holds n entries, and the tree has n nodes. The recursion depth is the height of the tree, at most n, and the lesson limits it to 400 levels.

Edge cases and common mistakes

One value. preorder = [-1] and inorder = [-1] gives [-1]: one node, and both child ranges are empty.
Only left children. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3]. Every value comes before its parent in inorder, so each node has only a left child.
Only right children. The same preorder with inorder = [1,2,3] gives [1,null,2,null,3].
Building the right subtree first. The counter would hand out the left subtree's roots to the right subtree, and the tree would come out wrong. Preorder is only consistent with left-then-right.
Passing the counter by value. Each call would advance its own copy, so after the left subtree is built the caller's counter would still point at the left subtree's root, and the right subtree would start from the wrong value.
Using hi = len(inorder). The range is inclusive, so the last index is len(inorder)-1. With the stop test lo > hi, an off-by-one here makes the helper read past the end of preorder and panic.
Repeated values. The map needs each value to have one index. That is why the statement guarantees that all values are different.

Testing

Results are printed level by level, with null for missing children.

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] gives [3,9,20,null,null,15,7].
preorder = [-1], inorder = [-1] gives [-1].
preorder = [1,2,3], inorder = [3,2,1] gives [1,2,null,3].
preorder = [1,2,3], inorder = [1,2,3] gives [1,null,2,null,3].
preorder = [1,2,4,5,3], inorder = [4,2,5,1,3] gives [1,2,3,4,5].
preorder = [2,1,3], inorder = [1,2,3] gives [2,1,3].

Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free