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

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). The recursive function uses preorder_index to track the current root in preorder and uses the inorder_map to partition the tree into left and right subtrees, recursively building each subtree.

Optimal Approach

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.

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

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)

1class Solution {
  private int preorderIndex;
  private Map<Integer, Integer> inorderMap;
4
  public TreeNode buildTree(int[] preorder, int[] inorder) {
      inorderMap = new HashMap<>();
      for (int i = 0; i < inorder.length; i++) {
          inorderMap.put(inorder[i], i);
      }
      preorderIndex = 0;
      return build(preorder, 0, inorder.length - 1);
  }
13
  private TreeNode build(int[] preorder, int left, int right) {
      if (left > right) {
          return null;
      }
18
      int rootVal = preorder[preorderIndex];
      preorderIndex++;
21
      TreeNode root = new TreeNode(rootVal);
      int inorderRootIndex = inorderMap.get(rootVal);
24
      root.left = build(preorder, left, inorderRootIndex - 1);
      root.right = build(preorder, inorderRootIndex + 1, right);
27
      return root;
  }
30}

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

4	`preorder_index = 0`

Objective

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

Key Insight

Preorder visits roots before their subtrees, so a shared index lets the recursion consume roots in exactly the required order.

Interview Quick-Check

Core Logic

The preorder index must advance exactly once per constructed node.

3

Start Recursive Construction from the Full Inorder Range

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

Objective

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

Key Insight

The whole reconstruction is just repeated rebuilding of smaller inorder slices. The initial call covers the complete slice.

Interview Quick-Check

Core Logic

The initial recursive call should span the entire inorder array.

4

Define Recursive Builder and Handle Empty Inorder Range

6def build(left, right):
  nonlocal preorder_index
  if left > right:
      return None

Objective

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

Key Insight

Each recursive call owns one inorder range. When the left boundary crosses the right boundary, that subtree does not exist.

Interview Quick-Check

Core Logic

An invalid inorder range means the current subtree is empty.

State & Boundaries

Returning None here is what correctly terminates leaf expansion.

5

Read Current Root and Find Its Inorder Split

11root_val = preorder[preorder_index]
12preorder_index += 1
14root = TreeNode(root_val)
15inorder_root_index = inorder_map[root_val]

Objective

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

Key Insight

Preorder gives the root immediately, and inorder tells where left subtree ends and right subtree begins. Those two traversals together determine the subtree structure.

Interview Quick-Check

Core Logic

Read the root from preorder before recursing into children.

State & Boundaries

The inorder index of the root is the split point between left and right subtrees.

6

Recursively Build Children and Return Subtree Root

17root.left = build(left, inorder_root_index - 1)
18root.right = build(inorder_root_index + 1, right)
20return root

Objective

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

Key Insight

Everything left of the root in inorder belongs to the left subtree, and everything right belongs to the right subtree. Recursing on those ranges reconstructs the exact original tree.

Interview Quick-Check

Core Logic

Use the root index to recurse on left and right inorder slices.

State & Boundaries

Return the root after attaching both children so parent calls can link the subtree correctly.

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.

Line 17 Critical

root.left = build(left, inorder_root_index - 1)

Recursively build the left subtree using the inorder range before the root.

The left subtree consists of all nodes in inorder before the root's index, so recursion on this range reconstructs the left subtree.

Line 18 Critical

root.right = build(inorder_root_index + 1, right)

Recursively build the right subtree using the inorder range after the root.

The right subtree consists of all nodes in inorder after the root's index, so recursion on this range reconstructs the right subtree.

Line 6 Core

def build(left, right):

Define the recursive builder for the current inorder range.

This helper defines the recursive construction over an inorder slice, which is the core decomposition used to rebuild the tree correctly.

Line 7 Core

nonlocal preorder_index

Declare preorder_index as nonlocal to modify it inside the nested build function.

This declaration allows the recursive function to update preorder_index across calls, ensuring the correct root node is selected at each step.

Line 8 Core

if left > right:

Check if the current inorder range is invalid, indicating no subtree.

This base case terminates recursion when the subtree boundaries cross, correctly handling empty subtrees.

Line 12 Core

preorder_index += 1

Increment preorder_index to move to the next root for subsequent recursive calls.

Incrementing preorder_index ensures the next recursive call processes the correct root node in preorder sequence.

Line 20 Core

return root

Return the constructed root node with attached left and right subtrees.

Returning the root node completes the current subtree construction, allowing parent calls to link subtrees correctly.

Line 4 Core

preorder_index = 0

Initialize preorder index to track the current root node in preorder traversal.

Maintaining a global preorder index allows the recursion to know which node to process next as the root, preserving preorder traversal order.

Line 9 Core

return None

Return None for empty subtree.

Returning None signals that there is no node to attach, correctly representing leaf nodes.

Line 14 Core

root = TreeNode(root_val)

Create a new TreeNode with the current root value.

This node becomes the root of the current subtree, linking left and right subtrees recursively.

Line 22 Core

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

Start the recursive tree construction with the full inorder range and return the final tree root.

This initial call triggers the entire recursive process, covering the whole tree and returning the reconstructed root.

Test Your Understanding

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

Because linear searches for each root in inorder would lead to O(n²) time complexity. Using a hash map reduces the lookup to O(1), enabling the entire tree to be reconstructed in O(n) time.

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)`

1	`class Solution {`
2	`private int preorderIndex;`
3	`private Map<Integer, Integer> inorderMap;`
4
5	`public TreeNode buildTree(int[] preorder, int[] inorder) {`
6	`inorderMap = new HashMap<>();`
7	`for (int i = 0; i < inorder.length; i++) {`
8	`inorderMap.put(inorder[i], i);`
9	`}`
10	`preorderIndex = 0;`
11	`return build(preorder, 0, inorder.length - 1);`
12	`}`
13
14	`private TreeNode build(int[] preorder, int left, int right) {`
15	`if (left > right) {`
16	`return null;`
17	`}`
18
19	`int rootVal = preorder[preorderIndex];`
20	`preorderIndex++;`
21
22	`TreeNode root = new TreeNode(rootVal);`
23	`int inorderRootIndex = inorderMap.get(rootVal);`
24
25	`root.left = build(preorder, left, inorderRootIndex - 1);`
26	`root.right = build(preorder, inorderRootIndex + 1, right);`
27
28	`return root;`
29	`}`
30	`}`

6	`def build(left, right):`
7	`nonlocal preorder_index`
8	`if left > right:`
9	`return None`

Problem

Example

Approach

Solution

Step-by-Step Solution

Build Hash Map for Constant-Time Inorder Index Lookup

Initialize Preorder Tracking State

Start Recursive Construction from the Full Inorder Range

Define Recursive Builder and Handle Empty Inorder Range

Read Current Root and Find Its Inorder Split

Recursively Build Children and Return Subtree Root

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.