Problem overview
buildTree receives two arrays of Int, preorder and inorder, both listing the values of the same binary tree, and returns the tree's root as a TreeNode?. All values are different. The lesson provides the TreeNode class, with val, left, right and init(_ x: Int).
In the first example, preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7]. The result, printed level by level, is [3,9,20,null,null,15,7]: 3 is the root, 9 is its left child, and 20 is its right child with the children 15 and 7.
Approach: the root comes first in preorder
Preorder lists a node, then its whole left subtree, then its whole right subtree. So the first value of preorder is always the root. Inorder lists the left subtree, then the node, then the right subtree. Once you know where the root sits in inorder, everything to its left is the left subtree and everything to its right is the right subtree.
Each subtree fills one unbroken stretch of inorder, so two indexes, lo and hi, describe it. In preorder, the roots appear in exactly the order the recursion needs them: this subtree's root, then the roots of the left subtree, then those of the right subtree. A single counter that moves forward through preorder therefore hands out the next root every time.
Finding the root's position in inorder by scanning would cost O(n) per node and O(n²) overall. Since the values are all different, a dictionary from value to inorder index answers in constant time, and the whole build is O(n).
Step by step
- The index map. A property
inorderIndex, an empty[Int: Int], will hold each value's position ininorder. A property is visible to every method of the class, so the helper can use it. - The preorder counter. A property
preIndexstarting at 0 marks the next root to use. - Fill the map. In
buildTree, loopiover0..<inorder.countand storeiunder the keyinorder[i]. - Start the build. Return what the helper
buildmakes frompreorderand the whole range ofinorder, from 0 toinorder.count - 1. - The helper's signature.
build(_ preorder: [Int], _ lo: Int, _ hi: Int) -> TreeNode?builds the subtree whose values fillinorder[lo...hi]. - Empty range. If
lo > hi, there are no values, so returnnil. This ends the recursion below every leaf. - Take the next root. Read
preorder[preIndex]intovalue, then movepreIndexforward by one. - Create the node for
value. - Find the split. Look up
inorderIndex[value]asmid. A dictionary lookup returns an optional, so!unwraps it; every value is in the map. - Left subtree. Call
buildfor the rangelotomid - 1and store the result innode.left. The left call comes first because its roots follow this node in preorder. - Right subtree. Call
buildformid + 1tohi. By now the left call has used all of its roots, sopreIndexpoints at the right subtree's root. - Return the node.
The solution in Swift
class Solution {
var inorderIndex = [Int: Int]()
var preIndex = 0
func build(_ preorder: [Int], _ lo: Int, _ hi: Int) -> TreeNode? {
if lo > hi {
return nil
}
let value = preorder[preIndex]
preIndex += 1
let node = TreeNode(value)
let mid = inorderIndex[value]!
node.left = build(preorder, lo, mid - 1)
node.right = build(preorder, mid + 1, hi)
return node
}
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
for i in 0..<inorder.count {
inorderIndex[inorder[i]] = i
}
return build(preorder, 0, inorder.count - 1)
}
}
The Swift details worth a closer look:
- Properties and
letnodes.Solutionis a class, so its methods can changepreIndexandinorderIndexwithout any special keyword.TreeNodeis a class too, solet node = TreeNode(value)still lets you assignnode.leftandnode.right:letfixes the reference, not the object's contents. - Optional from a dictionary.
inorderIndex[value]has typeInt?, because a missing key givesnil. The!would crash for a value that isn't in the map, which can't happen when the two arrays describe the same tree. - The order of the two recursive calls matters. The calls share
preIndex, which only works if the left subtree is built before the right one. Swapping the two lines gives wrong trees. - Passing arrays down. Arrays are value types, but passing
preordertobuilddoesn't copy the elements: Swift copies an array only when someone changes it, and nothing does here. - Ranges.
0..<inorder.countexcludes the upper bound, so the loop visits every index exactly once. The recursion uses inclusive bounds (loandhiare both valid indexes), which is why the empty case islo > hi.
Complexity
Time: O(n). Filling the map visits each index once. build creates exactly one node per value and does a constant amount of other work per call, plus one nil return per missing child.
Space: O(n). The dictionary holds n entries, and the tree itself has n nodes. The recursion is as deep as the tree, at most 400 levels here.
Edge cases and common mistakes
- A single value.
preorder = [-1]andinorder = [-1]give[-1]: both child ranges are empty. - Shapes that are all one side. With
preorder = [1,2,3],inorder = [3,2,1]gives[1,2,null,3](every node has only a left child), whileinorder = [1,2,3]gives[1,null,2,null,3]. - The same preorder, a different tree.
inorder = [2,1,3]withpreorder = [1,2,3]gives[1,2,3]. The inorder array alone decides where each root splits its range. - Using
midagainstpreorder.midis a position ininorder. The next root is found with the separate counterpreIndex. - Reusing one
Solutionobject.preIndexis never set back to 0, so after one call it points past the end ofpreorder. A secondbuildTreeon the same object reads out of bounds and crashes. Use a newSolutionfor each tree, or resetpreIndexto 0 at the start ofbuildTree. - Scanning for the root. Searching
inorderwith a loop for every node still works but takesO(n²)time.
Testing
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].
