Blind 75 · Trees

Construct Binary Tree from Preorder and Inorder Traversal

Medium

Problem

Given two integer arrays preorder and inorder — the preorder and inorder traversals of the same binary tree, with all values distinct — rebuild the tree and return its root.

Examples

Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Example 3:
Input: preorder = [1,2], inorder = [2,1]
Output: [1,2]

Example 4:
Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]

Constraints

1 <= preorder.length = inorder.length <= 3000
-3000 <= values <= 3000, all distinct

How to think about it

1. Preorder Names the Root, Inorder Splits the Rest Optimal

Intuition

Each traversal supplies half the answer and neither is enough alone. Preorder visits the root first, so its next unused value is always the root of whatever subtree you are building. Inorder puts everything left of the root in the left subtree and everything right of it in the right, so locating the root there splits the remaining values into exactly those two halves. Recurse on the halves in preorder order and the tree assembles itself. A map from value to inorder index turns the repeated search into a lookup, which is the whole difference between quadratic and linear.

Algorithm

1. Index every value by its position in inorder.
2. Walk preorder with a moving cursor; the value under it is the current root.
3. Look up that value's inorder position to find where the left subtree ends.
4. Build the left subtree from the inorder range before it, then the right from the range after — left first, because that is the order preorder consumes them.

Time & Space

Time O(n) with the index, O(n^2) without it from re-scanning inorder at every node. Space O(n).