Construct Binary Tree From Preorder And Inorder Traversal

preorder’s first element is always the current subtree’s root. Finding that same value in inorder splits the remaining values into “everything in the left subtree” (values before it) and “everything in the right subtree” (values after it) — exactly the information needed to recurse. The only question is how cheaply that split can be located and passed down.

Recursive with Slicing + Linear Search

Time O(n^2)Space O(n^2)

Take preorder[0] as the root, find it in inorder with .index(), then slice both arrays into left/right pieces and recurse.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        if not preorder:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        mid = inorder.index(root_val)
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

Complexity: .index() scans up to n elements at every one of n calls → O(n^2) time worst case, and slicing copies arrays at every level → O(n^2) space for all the slice copies combined.

Hashmap Index + Pointer (no slicing)

OptimalTime O(n)Space O(n)

Two changes remove the quadratic behavior: a hashmap from value to its index in inorder turns the “find the root” step into O(1), and a single shared pointer into preorder (rather than slicing it) tracks which element is “next” without copying arrays. Only the inorder range shrinks per call, via plain index bounds.

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        index_of = {val: i for i, val in enumerate(inorder)}
        self.pre_idx = 0

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

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

Tracing preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]: watch the shared preorder pointer advance exactly once per node while the inorder range shrinks around each root.

preorder · shared pointer

3920157

inorder · current range[0,4]

9315207

tree under construction

1 / 6

currentresultcomparing

build(0, 4) starts the root call: the whole inorder array is its range, and the preorder pointer sits at the first value, 3.

Complexity: each call does O(1) hashmap lookup work and the shared pointer visits each preorder element exactly once → O(n) time. The hashmap plus the recursion stack (which reaches O(n) depth on a skewed tree) → O(n) space.

Construct Binary Tree From Preorder And Inorder Traversal

Recursive with Slicing + Linear Search

Hashmap Index + Pointer (no slicing)

More Trees practice