How do you solve Construct Binary Tree from Preorder and Inorder Traversal?

Use a recursive DFS function that takes the current subtree boundaries in the inorder array. At each call, select the current root from preorder using preorder_index, increment preorder_index, find the root's index in inorder via the hash map, and recursively build left and right subtrees by adjusting the inorder boundaries. This approach reconstructs the tree in O(n) time and O(n) space.

What pattern does Construct Binary Tree from Preorder and Inorder Traversal use?

The Pattern: DFS (Recursive Tree Construction) The Heuristic: When reconstructing a tree from traversal orders, use preorder to identify roots and inorder to partition subtrees, recursively building the tree by narrowing the inorder boundaries and advancing preorder index.

Construct Binary Tree from Preorder and Inorder Traversal

Q: What is the time complexity of Construct Binary Tree from Preorder and Inorder Traversal?

O(n). Each node is processed exactly once. The hash map allows O(1) lookup of root positions in inorder, avoiding repeated linear scans. The recursion partitions the tree without overlap, resulting in linear time.

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.

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
−3000 ≤ preorder[i], inorder[i] ≤ 3000
preorder and inorder consist of unique values
Each value of inorder also appears in preorder
preorder is guaranteed to be the preorder traversal of the tree
inorder is guaranteed to be the inorder traversal of the tree

Example

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

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

The preorder traversal visits nodes in the order: root, left subtree, right subtree. The inorder traversal visits nodes in the order: left subtree, root, right subtree. The algorithm uses the first element in preorder as the root, finds its index in inorder to separate left and right subtrees, and recursively builds the tree. For the example, root is 3 (preorder[0]). In inorder, 3 is at index 1, so left subtree is inorder[0:1] = [9], right subtree is inorder[2:5] = [15,20,7]. Recursively, the left subtree root is 9, which has no children, and the right subtree root is 20, with left child 15 and right child 7. This recursive partitioning reconstructs the entire tree.

Approach

Straightforward Solution

A naive approach would repeatedly search for the root value in the inorder array using linear scans, resulting in O(n²) time complexity due to repeated searches for each subtree root.

Core Observation

The preorder traversal always starts with the root node, and the inorder traversal splits the tree into left and right subtrees around the root. This property allows recursive reconstruction by identifying the root and partitioning the inorder array accordingly.

Path to Optimal

Preview

To optimize, build a hash map from node values to their indices in the inorder array. This allows O(1) lookup of the root's position in inorder, reducing the overall complexity to O(n)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS function that takes the current subtree boundaries in the inorder array…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is processed exactly once. The hash map allows O(1) lookup of root positions in inorder, avoiding repeated linear scans. The recursion partitions the tree without overlap, resulting in linear time.

Space

O(n)

The hash map stores all n node indices. The recursion stack can go as deep as the height of the tree, which in the worst case is O(n). The output tree nodes also require O(n) space, but this is not auxiliary.

Solution

Python

1class Solution:
  def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:
      inorder_map = {val: i for i, val in enumerate(inorder)}
      preorder_index = 0
5
      def build(left, right):
          nonlocal preorder_index
          if left > right:
              return None
          
          root_val = preorder[preorder_index]
          preorder_index += 1
          
          root = TreeNode(root_val)
          inorder_root_index = inorder_map[root_val]
          
          root.left = build(left, inorder_root_index - 1)
          root.right = build(inorder_root_index + 1, right)
          
          return root
21
      return build(0, len(inorder) - 1)

Step-by-Step Solution

1

Build Hash Map for Constant-Time Inorder Index Lookup

3	`inorder_map = {val: i for i, val in enumerate(inorder)}`

Objective

To create a mapping from node values to their inorder indices so subtree boundaries can be located in constant time.

Key Insight

The inorder position of each root is what splits the tree into left and right subtrees. Precomputing that lookup prevents repeated linear scans and keeps reconstruction efficient.

Interview Quick-Check

Core Logic

Use a value-to-index map so the inorder split point is found in O(1).

Common Pitfalls & Bugs

Without this map, repeated searches through inorder push the solution toward quadratic time.

2

Initialize Preorder Tracking State

To initialize the shared preorder pointer that identifies the next subtree root during recursion.

3

Start Recursive Construction from the Full Inorder Range

To launch the recursive builder over the entire inorder segment representing the full tree.

4

Define Recursive Builder and Handle Empty Inorder Range

To define the recursive helper and stop immediately when the current inorder segment is empty.

5

Read Current Root and Find Its Inorder Split

To take the next root from preorder, advance the shared index, create the node, and locate its inorder position.

6

Recursively Build Children and Return Subtree Root

To recursively construct the left and right subtrees using the split inorder ranges and then return the completed root.

5 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 3 Critical

inorder_map = {val: i for i, val in enumerate(inorder)}

Create a hash map from node values to their indices in inorder traversal.

This map enables O(1) lookup of any node's position in inorder, which is essential to partition the tree efficiently and avoid repeated linear scans.

Line 11 Critical

root_val = preorder[preorder_index]

Select the current root value from preorder traversal.

Preorder traversal visits root first, so preorder_index points to the root of the current subtree, enabling correct tree reconstruction.

Line 15 Critical

inorder_root_index = inorder_map[root_val]

Find the index of the root in inorder traversal using the hash map.

Locating the root in inorder divides the tree into left and right subtrees, enabling recursive partitioning.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why is it necessary to use a hash map for inorder indices instead of searching linearly each time?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Construct Binary Tree from Preorder and Inorder Traversal from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Construct Binary Tree from Preorder and Inorder Traversal drill

or drill a free problem

1	`class Solution:`
2	`def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:`
3	`inorder_map = {val: i for i, val in enumerate(inorder)}`
4	`preorder_index = 0`
5
6	`def build(left, right):`
7	`nonlocal preorder_index`
8	`if left > right:`
9	`return None`
10
11	`root_val = preorder[preorder_index]`
12	`preorder_index += 1`
13
14	`root = TreeNode(root_val)`
15	`inorder_root_index = inorder_map[root_val]`
16
17	`root.left = build(left, inorder_root_index - 1)`
18	`root.right = build(inorder_root_index + 1, right)`
19
20	`return root`
21
22	`return build(0, len(inorder) - 1)`