Build Tree from Preorder and Inorder

1. Step 1: Initialize Solution.buildTree

   Replace the empty starter with the first real state owned by Solution.buildTree. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Left Chain case

   Complete the readable core algorithm for one representative Interview case. Consume preorder roots in order and split inorder intervals through an index map.

4. Step 4: Harden the Sample boundary

   Repair the reviewed boundary and pass the complete submission contract. Preorder cursor always identifies the current subtree root. Its inorder position uniquely divides left and right subtree values; recursive construction in preorder order therefore rebuilds exactly the original tree.

• Do not repeatedly slice and linearly search inorder; that can become quadratic.
• trees and graphs
• hashing and sets

• LeetCode 105 — Construct Binary Tree from Preorder and Inorder Traversal

• Partition Traversal Ranges(opens in a new tab)

  Partition Traversal Ranges isolates each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. That focused state discipline is required when implementing build tree preorder inorder as a complete Interview Problem.

Map inorder values to indices, keep a shared preorder cursor, and recursively build inclusive inorder intervals root-left-right.

Why it works: Preorder cursor always identifies the current subtree root. Its inorder position uniquely divides left and right subtree values; recursive construction in preorder order therefore rebuilds exactly the original tree.

class Solution:
    def buildTree(self, preorder, inorder):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        positions = {value:index for index,value in enumerate(inorder)}
        preorder_index = 0
        def build(left, right):
            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)

• Build Tree from Inorder and Postorder(opens in a new tab)