Preorder visits a node first, then its whole left subtree, then its whole right subtree. So the first value of any subtree is its root. Inside one call of build, the next unused value preorder[pre_idx] is the root of the subtree that call must build.

Inorder visits the left subtree, then the node, then the right subtree. So the root sits between its two subtrees. Because all values are distinct, mid = where[root.val] is one exact index. The values inorder[lo..mid-1] are the left subtree, and the values inorder[mid+1..hi] are the right subtree.

Each call uses exactly one value of preorder for each node in its range. When build(lo, mid - 1) returns, pre_idx has moved past the whole left subtree. It now points at the root of the right subtree, which is what build(mid + 1, hi) needs.

Example: in Construct Binary Tree from Preorder and Inorder Traversal (LC 105), preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7] give the tree [3, 9, 20, null, null, 15, 7]. The root is 3. Inorder has [9] on its left and [15, 20, 7] on its right.

The board replays the example. Each node is drawn above its index in inorder, so the range of a subtree is always a block of neighbours. A node appears when its call creates it.

build(0, 4) uses preorder[0] = 3. Its index in inorder is 1, so the left range is [0..0] and the right range is [2..4]. The left call uses preorder[1] = 9, whose range [0..0] splits into two empty ranges. Then pre_idx is 2.

The right call build(2, 4) now reads preorder[2] = 20. This is correct only because the left call has used exactly the values of its own subtree. Then 15 and 7 are the roots of the two ranges inside [2..4]. At the end, pre_idx is 5, which is the number of values.

For 5 nodes there are 11 calls: 5 calls create a node and 6 calls get an empty range. A tree with N nodes always has N calls that create a node and N + 1 calls with an empty range.

pre_idx hands out roots in preorder order. Preorder lists the whole left subtree before the right subtree. So the left call must run first.

Suppose the right call runs first. For the example, build(0, 4) creates the root 3, and then build(2, 4) takes preorder[1] = 9. The value 9 is at inorder index 0, which is outside the range [2..4]. The call builds a wrong node, and the later calls read past the end of preorder. Python raises an IndexError.

pre_idx must also be one shared counter. If it is passed down as an argument, the right call starts right after its parent, as if the left subtree were empty. The call has no way to know how many values the left call used.

The empty test must be lo > hi. The range lo == hi has one value, which is a leaf. With lo >= hi, every leaf returns None and does not use its preorder value. On the example, the result is [3, null, 9, null, 20, 15], which is wrong.

The dictionary where is built once, so each split costs O(1). Each of the N values makes one node and two calls, so the time is O(N). The space is O(N) for where, plus O(H) for the recursion stack, where H is the height of the tree.

inorder.index(root.val) gives the same answer, but each call scans the list. For a tree shaped like a chain of 1000 nodes, the scans compare 500500 values in total, and the dictionary does 1000 lookups.

Inorder and postorder is the same idea, as in Construct Binary Tree from Inorder and Postorder Traversal (LC 106). Postorder writes the root last, so read it from the end, and build the right subtree first. Preorder and postorder, as in Construct Binary Tree from Preorder and Postorder Traversal (LC 889), do not fix one tree in general, so that problem has extra rules.

With one list only, the preorder of a binary search tree, the sorted order replaces inorder. Then the idea of the Bounds card applies, as in Construct Binary Search Tree from Preorder Traversal (LC 1008).