Construct Tree From Preorder and Inorder Traversal

Rebuild a binary tree from its preorder and inorder value lists. Values are unique.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Construct Tree From Preorder and Inorder Traversal: The next preorder value becomes a root, and its inorder position partitions the exact ranges passed to its left and right recursive calls.

Input and goalRebuild a binary tree from its preorder and inorder value lists. Values are unique.

Initialize traversal stateBuild the inorder position map, set preorder_index=0, and call build(0,4).

3current root 3/\920/\157

activeRoot3preorder[3, 9, 20, 15, 7]inorder[9, 3, 15, 20, 7]positions9:0, 3:1, 15:2, 20:3, 7:4callStackbuild(0,4)preorderIndex0

Recognize it

Unique node values are given in preorder and inorder, so root order and left/right membership complement each other to determine one binary tree.

Keep true

build(left,right) consumes exactly the next preorder values belonging to inorder[left:right+1] and returns precisely that subtree. Empty ranges consume nothing and return None.

Reuse it

Combine one traversal that selects the next root with another that partitions membership, and recurse on index ranges; the same decomposition works with inorder plus postorder by choosing roots from the opposite end.

Pattern: Preorder chooses roots and inorder splits child ranges.

Simple idea: The next preorder value is the current root. Its inorder position separates the left and right subtrees. A map makes that position lookup constant time.

def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
   positions = {value: index for index, value in enumerate(inorder)}
   preorder_index = 0

   def build(left: int, right: int) -> TreeNode | None:
      nonlocal preorder_index
      if left > right:
         return None

      value = preorder[preorder_index]
      preorder_index += 1
      node = TreeNode(value)
      middle = positions[value]
      node.left = build(left, middle - 1)
      node.right = build(middle + 1, right)
      return node

   return build(0, len(inorder) - 1)

Cost: $O(n)$ time and $O(n)$ space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.