Construct Binary Tree from Preorder and Inorder Traversal

Solving tips

Recognize this as divide-and-conquer: preorder[0] is always the root, and its position in inorder splits the remaining values into left- and right-subtree ranges.
Precompute a value to inorder-index hash map once so you locate each root in O(1); this is what turns the naive O(n^2) into O(n) time, O(n) space.
Pass index ranges (or use one global preorder pointer advancing left-then-right) instead of slicing arrays, which reintroduces O(n^2) copying.
Pitfall: the off-by-one when splitting preorder — the left range starts at pre_lo+1 (skip the root), and its size equals the count of inorder values left of the root.

Problem

You are given two integer arrays for the same binary tree: preorder (values in preorder-traversal order) and inorder (values in inorder-traversal order). All values are distinct. Reconstruct the tree and return its root.

Recall: preorder visits node, left subtree, right subtree; inorder visits left subtree, node, right subtree.

Examples

Example 1

Input:  preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: the tree

        3
       / \
      9   20
         /  \
        15   7

The first preorder value (3) is the root; in inorder, [9] sits left of 3 (left subtree) and [15, 20, 7] sits right (right subtree).

Example 2

Input:  preorder = [-1], inorder = [-1]
Output: single node -1

One element, one node.

Example 3

Input:  preorder = [1, 2, 3], inorder = [3, 2, 1]
Output: a left-leaning chain: 1's left child is 2, 2's left child is 3

Root 1 sits at the end of inorder, so everything is in its left subtree; recursing repeats the shape.

Constraints

1 <= preorder.length <= 3000, inorder.length == preorder.length
-3000 <= values <= 3000, all values distinct
Both arrays are valid traversals of one tree.
Expected complexity: O(n) time with a hash map; naive slicing is O(n^2).

Think about it first

Hint 1

What does the very first element of `preorder` tell you, with zero work?

Hint 2

Locate that root value in `inorder`. Its index splits `inorder` into left-subtree values and right-subtree values — and the count of left values tells you where `preorder` splits too.

Hint 3

Recurse on the two halves. For `O(n)`: build a value→index map of `inorder` once, and consume `preorder` left-to-right with a single moving pointer (build left subtree before right), so you never search or slice.

TL;DR

Divide & conquer — first preorder element is the root, split inorder around it; with a value→index hash map it’s O(n) time, O(n) space.

Approach 1 — Brute force: slice and recurse

The naive intuition: preorder[0] is the root. Find it in inorder with a linear scan; the elements before it form the left subtree, the ones after form the right. Slice both arrays and recurse.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])       # O(n) scan
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

Complexity: O(n^2) time and space in the worst case — a skewed tree makes every level pay a full-length index scan plus slice copies. At n = 3000 that’s millions of copied elements; it passes, but it’s the answer interviewers expect you to improve.

Approach 2 — Hash map + index ranges (no slicing)

The insight: the two quadratic costs are the linear search and the slicing. Precompute value → inorder index once, and pass index ranges down the recursion instead of copies. The left subtree’s size (mid - in_lo) tells you exactly how to partition the preorder range.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


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

        def build(pre_lo: int, pre_hi: int, in_lo: int, in_hi: int) -> Optional[TreeNode]:
            # ranges are inclusive
            if pre_lo > pre_hi:
                return None
            root = TreeNode(preorder[pre_lo])
            mid = idx[preorder[pre_lo]]
            left_size = mid - in_lo
            root.left = build(pre_lo + 1, pre_lo + left_size, in_lo, mid - 1)
            root.right = build(pre_lo + left_size + 1, pre_hi, mid + 1, in_hi)
            return root

        n = len(preorder)
        return build(0, n - 1, 0, n - 1)

Walkthrough on Example 1 (preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]):

build(0,4, 0,4): root 3, mid = 1, left_size = 1.
Left: build(1,1, 0,0) → leaf 9.
Right: build(2,4, 2,4): root 20, mid = 3, left_size = 1.
Its left: build(3,3, 2,2) → leaf 15. Its right: build(4,4, 4,4) → leaf 7.
Result: 3(9, 20(15, 7)).

Complexity: O(n) time (constant work per node after the O(n) map build); O(n) space for the map plus O(h) recursion stack.

Approach 3 — Single moving preorder pointer (elegant variant)

The insight: preorder is root, left, right — exactly the order a preorder-style recursion wants its roots. So one global pointer walking preorder left to right always points at the next subtree root, as long as you build left before right. Only inorder boundaries are needed to detect empty subtrees.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


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

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

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

Walkthrough on Example 1: consume 3 (mid=1) → left over [0..0]: consume 9 → back; right over [2..4]: consume 20 (mid=3) → its left [2..2]: consume 15 → its right [4..4]: consume 7. The pointer sweeps preorder exactly once, in order.

Complexity: O(n) time, O(n) space (map + recursion stack up to O(h)).

Common pitfalls

Off-by-one splitting preorder in Approach 2: the left range is pre_lo + 1 .. pre_lo + left_size — forgetting the +1 (skipping the root) is the classic bug.
In Approach 3, recursing right before left — the moving pointer only works in root, left, right order (the mirror of the postorder variant, which goes right first).
Using inorder.index(...) inside the recursion even after building the map — silently reintroduces O(n^2).
This construction requires distinct values; with duplicates the inorder split is ambiguous.

Pattern takeaway

Preorder+inorder and postorder+inorder are mirror twins of one template: the order-giving array (preorder from the front, postorder from the back) supplies roots one at a time, and inorder tells you how many nodes each side gets. The linear-time trick is always the same pair — hash the inorder positions, and replace slices with index ranges or a single consuming pointer whose recursion order matches the array’s root order.