Why is inorder required along with preorder?

Preorder identifies the root but does not reveal where the left subtree ends and the right subtree begins. The root's inorder position separates these two portions.

Why must the left subtree be constructed before the right subtree?

After the root, preorder contains all nodes belonging to the left subtree before nodes belonging to the right subtree. Therefore, preIndex naturally progresses through the left subtree first.

Why are distinct node values required?

Distinct values ensure that every root has one unique position in inorder. With duplicate values, the correct subtree boundary cannot always be determined from the value alone.

What happens when inStart > inEnd?

The current inorder interval contains no nodes, so that child subtree does not exist and null is returned.

What improvement does the hash map provide?

Without the hash map, the root position may need to be searched linearly for every recursive call, producing O(N²) worst-case time. Precomputing the inorder positions reduces the reconstruction to O(N) time.

Construct a Binary Tree from Preorder and Inorder

Given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of the same binary tree, construct and return the original binary tree.

All node values are distinct, and both traversals contain the same set of values.

Recall:

Preorder → Root, Left, Right

Inorder → Left, Root, Right

Example 1

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

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

Explanation:
The first preorder value 3 becomes the root. Its position in inorder separates node 9 into the left subtree and nodes 15, 20, 7 into the right subtree. Repeating the same process reconstructs the complete tree.

Example 2

Input:
preorder = [1, 2, 4, 5, 3]
inorder = [4, 2, 5, 1, 3]

Output:
[1, 2, 3, 4, 5]

Explanation:
Node 1 is identified as the root from preorder. Its inorder position separates [4, 2, 5] as the left subtree and [3] as the right subtree.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

Preorder traversal provides the most important information first: the root of the current subtree.

Once that root is located in inorder, the inorder traversal divides the current subtree into:

Left Subtree | Root | Right Subtree

This process can then be repeated recursively.

A variable named preIndex is maintained to represent the index of the next unused element in preorder. Since preorder always visits the root before its children, preorder[preIndex] always gives the root of the subtree currently being constructed.

Two variables, inStart and inEnd, represent the boundaries of the portion of the inorder array belonging to the current subtree. These boundaries prevent recursive calls from processing nodes that belong to some other subtree.

For every newly selected root, its position is searched linearly between inStart and inEnd. This correctly divides the current subtree into its left and right portions.

The repeated linear search makes this approach inefficient in the worst case.

Algorithm

A variable preIndex is initialized to 0 so that it points to the next unused root value in preorder.
The variables inStart and inEnd are used to represent the current valid range in inorder from which a subtree must be constructed.
If inStart > inEnd, null is returned because no nodes belong to that subtree.
The value at preorder[preIndex] is selected as the current root, and preIndex is incremented so that the next preorder value can be used by a later recursive call.
The current root value is searched linearly within the inorder range [inStart, inEnd], and its position is used to divide the range into left and right subtree portions.
The left subtree is recursively constructed from [inStart, rootIndex - 1].
The right subtree is recursively constructed from [rootIndex + 1, inEnd].
After both child links have been assigned, the current root is returned to the parent recursive call.

Dry Run

Construct a Binary Tree from Preorder and Inorder Brute Force Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  int preIndex;
19
  // Builds the tree using the current inorder range.
  TreeNode* build(
      vector<int>& preorder,
      vector<int>& inorder,
      int inStart,
      int inEnd
  ) {
      if (inStart > inEnd) {
          return nullptr;
      }
30
      // preorder[preIndex] is the root
      // of the current subtree.
      int rootValue = preorder[preIndex++];
      TreeNode* root = new TreeNode(rootValue);
35
      int rootIndex = inStart;
37
      // The root position splits inorder
      // into left and right subtree ranges.
      while (
          rootIndex <= inEnd &&
          inorder[rootIndex] != rootValue
      ) {
          rootIndex++;
      }
46
      root->left = build(
          preorder,
          inorder,
          inStart,
          rootIndex - 1
      );
53
      root->right = build(
          preorder,
          inorder,
          rootIndex + 1,
          inEnd
      );
60
      return root;
  }
63
64public:
  // Reconstructs the binary tree from
  // preorder and inorder traversals.
  TreeNode* buildTree(
      vector<int>& preorder,
      vector<int>& inorder
  ) {
      preIndex = 0;
72
      return build(
          preorder,
          inorder,
          0,
          inorder.size() - 1
      );
  }
80};
81
82int main() {
  vector<int> preorder = {3, 9, 20, 15, 7};
  vector<int> inorder = {9, 3, 15, 20, 7};
85
  Solution solution;
87
  TreeNode* root =
      solution.buildTree(preorder, inorder);
90
  return 0;
92}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the constructed tree.

Time Complexity: O(N²) in the worst case. For each of the N nodes, its position may be searched linearly in the current inorder range. In a skewed tree, these searches can have sizes N, N-1, N-2, ..., resulting in quadratic time.

Space Complexity: O(H), where H is the height of the constructed binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Optimal Approach

The expensive operation in the brute-force approach is repeatedly searching for each root inside the inorder traversal.

Because all values are distinct, every value has exactly one position in inorder. Therefore, a hash map can be created before reconstruction begins:

node value → inorder index

This allows each root position to be found in O(1) average time.

The variable preIndex again represents the index of the next unused preorder value. Since preorder follows Root → Left → Right, the value at preorder[preIndex] is always the root of the current subtree.

The variables inStart and inEnd represent the left and right boundaries of the inorder section belonging to that subtree. Once the current root's inorder index is obtained from the hash map, these boundaries can be divided directly into the ranges belonging to the left and right subtrees.

Therefore:

preorder determines which node becomes the root,
inorder determines which nodes belong to its left and right subtrees.

Each node is created exactly once, and repeated inorder scanning is eliminated.

Algorithm

A hash map is constructed so that the inorder index of every node value can be accessed directly.
A variable preIndex is initialized to 0 so that the next unused value in preorder can be selected as the root of each subtree.
The variables inStart and inEnd are used to represent the inorder interval belonging to the subtree currently being constructed.
If inStart > inEnd, null is returned because the current inorder interval contains no nodes.
A new node is created using preorder[preIndex], and preIndex is incremented so that the next preorder value becomes available.
The inorder position of the current root is obtained from the hash map in O(1) average time.
The left subtree is recursively constructed using the inorder interval [inStart, rootIndex - 1].
The right subtree is recursively constructed using [rootIndex + 1, inEnd].
After both subtrees have been attached, the current root is returned.

Dry Run

Construct a Binary Tree from Preorder and Inorder Optimal Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  int preIndex;
  unordered_map<int, int> inorderIndex;
20
  // Builds a subtree using its valid
  // interval in the inorder traversal.
  TreeNode* build(
      vector<int>& preorder,
      int inStart,
      int inEnd
  ) {
      if (inStart > inEnd) {
          return nullptr;
      }
31
      // preIndex points to the next root
      // available in preorder.
      int rootValue = preorder[preIndex++];
      TreeNode* root = new TreeNode(rootValue);
36
      // The stored inorder position divides
      // the current subtree into two ranges.
      int rootIndex =
          inorderIndex[rootValue];
41
      root->left = build(
          preorder,
          inStart,
          rootIndex - 1
      );
47
      root->right = build(
          preorder,
          rootIndex + 1,
          inEnd
      );
53
      return root;
  }
56
57public:
  // Reconstructs the tree using constant-time
  // average lookup of inorder positions.
  TreeNode* buildTree(
      vector<int>& preorder,
      vector<int>& inorder
  ) {
      preIndex = 0;
      inorderIndex.clear();
66
      // Each value is mapped to its unique
      // position in the inorder traversal.
      for (int i = 0; i < inorder.size(); i++) {
          inorderIndex[inorder[i]] = i;
      }
72
      return build(
          preorder,
          0,
          inorder.size() - 1
      );
  }
79};
80
81int main() {
  vector<int> preorder = {3, 9, 20, 15, 7};
  vector<int> inorder = {9, 3, 15, 20, 7};
84
  Solution solution;
86
  TreeNode* root =
      solution.buildTree(preorder, inorder);
89
  return 0;
91}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the constructed tree.

Time Complexity: O(N), where N is the number of nodes in the tree. The inorder index map is built once in O(N) time, and every node is created exactly once with O(1) average-time lookup of its inorder position.

Space Complexity: O(N + H). The inorder index map stores N entries, while the recursion stack requires O(H) space. Since H ≤ N, the overall auxiliary space is O(N).

Interview follow-up Questions

Preorder follows Root → Left → Right, so the first unused value in preorder is always the root of the subtree currently being constructed.

Construct a Binary Tree from Preorder and Inorder

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree

Construct a Binary Tree from Preorder and Inorder

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why does preorder help identify the root?

Why is inorder required along with preorder?

Why must the left subtree be constructed before the right subtree?

Why are distinct node values required?

What happens when inStart > inEnd?

What improvement does the hash map provide?

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree