The machine must rebuild the original binary tree from its preorder and inorder traversal arrays. The two traversals are complementary: preorder tells the machine which node comes first, and inorder tells the machine exactly how the tree splits into left and right sides.
The key insight is that the first element of preorder is always the root of the current subtree, and its position in the inorder array splits the inorder slice into the left subtree's nodes and the right subtree's nodes. Recursing on those two pairs of slices — with the same preorder prefix consumed — rebuilds the whole tree.
The approach has three steps. First, pop the next value from the front of the preorder stream and make it the root; if the stream is empty, return None. Second, find that value's index in the current inorder slice — a value-to-index map makes this O(1) instead of a scan. Third, recurse left with the inorder slice before the index and recurse right with the slice after it, returning the root. Each node is built once, so time is O(n) and space is O(n) for the map and recursion stack.
The trickiest edge case is that the recursion must consume the preorder stream in strict order — left subtree first, then right — because preorder visits the left subtree's nodes before the right subtree's. Using a single shared index rather than per-call slices of preorder avoids skipping nodes.
def buildTree(preorder, inorder):
index = {v: i for i, v in enumerate(inorder)}
it = iter(preorder)
def build(lo, hi):
if lo > hi:
return None
root = TreeNode(next(it))
mid = index[root.val]
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(inorder) - 1)