Construct Binary Tree from Preorder and Inorder Traversal

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Examples

The brute-force approach

Recursively: preorder[0] is always the root. Find the root in inorder to split into left and right subtrees. Recurse on each half.

def build(pre_start, pre_end, in_start, in_end):
    if pre_start > pre_end: return None
    root_val = preorder[pre_start]
    root = TreeNode(root_val)
    idx = inorder.index(root_val)    # linear search in inorder
    left_size = idx - in_start
    root.left = build(pre_start+1, pre_start+left_size, in_start, idx-1)
    root.right = build(pre_start+left_size+1, pre_end, idx+1, in_end)
    return root

O(n²) — linear search in inorder for each root. Precompute a hash map for O(n) total.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

If preorder[0] is the root, and you find its position in inorder, what does everything to its left in inorder represent? Everything to its right?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.