Construct Binary Tree from Preorder and Inorder Traversal

Intuition

Preorder visits the root first, so the very first unused preorder value is always the root of the current subtree. In inorder, that root sits between its left subtree (to the left) and its right subtree (to the right). Once we know the root's position in inorder, every value to its left belongs to the left subtree and every value to its right belongs to the right subtree. Scanning inorder for the root on each call would cost O(n) per node, so we precompute a hash map from value to inorder index for O(1) lookups. Advancing a single shared preorder pointer as we build lets us hand out roots in exactly the order preorder demands.

Algorithm walkthrough

1. 1Build a hash map that maps each inorder value to its index, and initialize a preorder pointer at 0.
2. 2Define a recursive helper that receives the inorder bounds [left, right] of the current subtree.
3. 3If left exceeds right the range is empty, so return null.
4. 4Take the value at the preorder pointer as the root and advance the pointer, then look up its inorder index mid in the map.
5. 5Recurse on [left, mid - 1] to build the left subtree, then on [mid + 1, right] for the right subtree so the order matches how preorder consumes roots.
6. 6Return the assembled root; the top-level call spans the entire inorder range.

Implementation

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(inorder)}
        self.pre = 0

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            root_val = preorder[self.pre]
            self.pre += 1
            root = TreeNode(root_val)
            mid = idx[root_val]
            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)
            return root

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