Construct Binary Tree from Preorder and Inorder Traversal

def buildTree(preorder, inorder):
    where = {v: i for i, v in enumerate(inorder)}
    nxt = 0
    def build(lo, hi):
        nonlocal nxt
        if lo > hi:
            return None
        root = TreeNode(preorder[nxt])
        nxt += 1
        mid = where[root.val]
        root.left = build(lo, mid - 1)
        root.right = build(mid + 1, hi)
        return root
    return build(0, len(inorder) - 1)

Construct Binary Tree from Preorder and Inorder Traversal. You get two lists from one tree. Preorder lists the root, then the left subtree, then the right. Inorder lists the left subtree, then the root, then the right. Rebuild the tree.

Preorder is three, nine, twenty, fifteen, seven. Inorder is nine, three, fifteen, twenty, seven. Together: three on top, nine on its left, twenty on its right, and fifteen and seven under twenty.

The simple way takes the first preorder value as the root, and scans inorder to find it. Values before it go left, values after it go right. On a lopsided tree, each scan walks almost the whole list: order n squared.

The fix: map each value to its inorder position, once. Now finding a root is one lookup. And the next preorder value is always the next root, if we build the left side before the right.

The code builds the map, then recurses on an inorder range. An empty range means no node. Otherwise, take the next preorder value, look up where it splits the range, build the left, then the right.

Three comes first: the root. It sits at position one in inorder, so nine goes left, and fifteen, twenty and seven go right. Next, nine: alone, a leaf. Next, twenty, at position three: fifteen goes left, seven goes right. The tree is rebuilt.

Each value is placed once, with one lookup: order n time. The map and the recursion take order n space.

Preorder picks the root, inorder splits the sides. That's Construct Binary Tree from Preorder and Inorder Traversal.