Hack University
105/670

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

A binary tree was walked twice and only the two visit orders survive: preorder (root, then left subtree, then right subtree) and inorder (left subtree, then root, then right subtree). All node values are distinct, and together the two sequences pin down exactly one tree.

Your function receives the two integer arrays preorder and inorder and must rebuild that tree, returning its root node. Create nodes with TreeNode(value) and hang subtrees on their left and right fields.

The key observation: preorder[0] is always the root, and finding that value inside inorder splits the remaining values into the left subtree (everything before it) and the right subtree (everything after it).

How the two traversals pin down the root and its subtreesPreorder's first value (3) is the root; the same value inside inorder separates the left subtree [9] from the right subtree [15, 20, 7]. Recursing on each side rebuilds the whole tree.
preorder — root comes firstinorder — root splits left | right39201579315207← left subtreeright subtree →3920157

Example 1:

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

Output: [3, 9, 20, null, null, 15, 7]

Explanation: Preorder starts with 3, so 3 is the root. In inorder, [9] sits left of 3 and [15, 20, 7] sits right, so 9 becomes the left subtree and recursing on [20, 15, 7] / [15, 20, 7] builds the right one: 20 with children 15 and 7.

Example 2:

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Explanation: One value, one node: the tree is a lone root holding -1.

Constraints:

  • 1 ≤ preorder.length ≤ 3000
  • inorder.length == preorder.length
  • -3000 ≤ node values ≤ 3000
  • All values are distinct; inorder is a permutation of preorder, and both come from one valid binary tree.

Hints:

What does the very first element of preorder tell you, no matter what the tree looks like? And where does that value land inside inorder?

Locating preorder[0] in inorder splits inorder into the left and right subtrees — and their sizes tell you how to split the rest of preorder. Recurse on the two halves. To go fast, precompute value → inorder index in a hash map and consume preorder with a single moving pointer instead of slicing arrays.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

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

Expected output: [3, 9, 20, null, null, 15, 7]