How do preorder and inorder traversals determine a binary tree?

Preorder visits a root before its subtrees, so its first value is the root. Inorder visits the left subtree, then the root, then the right subtree, so everything before the root's inorder position is its left subtree and everything after is its right. Repeating this on each part rebuilds the tree, provided the values are unique.

Why use a hash map of inorder indexes?

Each call needs the root's position in inorder. Scanning for it costs O(n) per call and O(n²) overall on a skewed tree. Mapping every value to its index first makes each lookup O(1), so the whole build is O(n).

Why must the left subtree be built before the right?

The recursion reads preorder with a single moving index. Preorder lists a root, then its whole left subtree, then its right subtree, so the left subtree must consume its values first or the right subtree would take the wrong roots.

Construct Binary Tree from Preorder and Inorder Traversal

Rebuild a binary tree from its preorder and inorder traversals: preorder names each root, and the root's inorder position splits its left and right subtrees.

MediumSolve on LeetCode

Problem Understanding

Construct Binary Tree from Preorder and Inorder Traversal: given two integer arrays preorder and inorder of the same tree, with unique values, rebuild and return the tree.

Example: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] gives the tree [3, 9, 20, null, null, 15, 7].

Attempt 1: Slice and Search

Take preorder[0] as the root, find it in inorder with a linear scan, slice both arrays into left and right parts and recurse. It is correct, but every call scans and copies — O(n²) time on a skewed tree, and O(n²) memory in the slices.

The Intuition: Preorder Names Roots, Inorder Splits Them

Two facts about the traversals:

Preorder is root, left subtree, right subtree. Reading it left to right gives the roots in exactly the order a depth-first build needs them.
Inorder is left subtree, root, right subtree. Once you know a root, its position mid in inorder splits the range: [lo, mid − 1] is its left subtree and [mid + 1, hi] its right.

So keep one index next into preorder, and write build(lo, hi) over an inorder range: an empty range is null; otherwise read the root, look up mid in a value → index map, build the left range, then the right. Building left before right matters, because preorder lists the whole left subtree before the right one.

Interactive Walkthrough

PREORDER GIVES ROOTS · INORDER SPLITS THEM

MAP INORDER INDEXES

preorder

inorder

Range

0..4

Built

0/5

call stack

No calls in progress

Map each inorder value to its index, then build the whole range, inorder[0..4]

preorder[0] = 3 is the root of [9, 3, 15, 20, 7]. It sits at inorder 1: 1 value left of it, 3 right

Tree

Enter any tree with unique values; its preorder and inorder are derived for you. The preorder pointer moves one root at a time, the current call's inorder range is filled with the root's position marked, and the tree below grows one node per root read.

Dry Run Table

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

`next`	Root	Inorder range	`mid`	Left range	Right range
0	3	`[9, 3, 15, 20, 7]`	1	`[9]`	`[15, 20, 7]`
1	9	`[9]`	0	empty	empty
2	20	`[15, 20, 7]`	3	`[15]`	`[7]`
3	15	`[15]`	2	empty	empty
4	7	`[7]`	4	empty	empty

Every preorder value is used once; the result is [3, 9, 20, null, null, 15, 7].

The Solution Template

A preorder index, an inorder index map and recursion over inorder ranges.

Construct Binary Tree from Preorder and Inorder Traversal Code

1var buildTree = function(preorder, inorder) {
2    const index = new Map();
3    inorder.forEach((val, i) => index.set(val, i));
4    let next = 0;
5
6    const build = (lo, hi) => {
7        if (lo > hi) return null;
8        const val = preorder[next++];
9        const root = new TreeNode(val);
10        const mid = index.get(val);
11        root.left = build(lo, mid - 1);
12        root.right = build(mid + 1, hi);
13        return root;
14    };
15
16    return build(0, inorder.length - 1);
17};

Edge Cases & Common Mistakes

One node: the root is built and both ranges are empty.
A skewed tree ([3, 2, null, 1]): every split puts all remaining values on one side — the map keeps it O(n) instead of O(n²).
Building right before left: the shared preorder index would hand the right subtree the left subtree's roots.
Duplicate values: the inorder position is ambiguous; the problem guarantees unique values.
Slicing arrays: correct, but copies cost O(n) per level — pass index ranges instead.
The C array offset: LeetCode limits values to −3000..3000, so val + 3000 indexes a fixed array instead of a hash map.

Summary

Read roots from preorder one at a time, and split each inorder range at the root's index — left subtree first, then right. With a value → index map, O(n) time and O(n) space.

Kth Smallest Element in a BST

Binary Tree Tilt