Log inSign up
mediumleetcodeNot Started

Construct Binary Tree from Preorder and Inorder Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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.

Example 1 · Example 1: Standard Tree:

Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] Tree: 3 / \ 9 20 / \ 15 7
Output: [3, 9, 20, null, null, 15, 7]
Explanation: 3 is root. Left child is 9. Right subtree is [20, 15, 7].

Example 2 · Example 2: Single Node:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: Single node tree.

Constraints:

  • 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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Decompose tree reconstruction into recursive divide and conquer.
  • Use hash map for O(1) index discovery.
  • Maintain precise array pointer boundaries without cloning arrays.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reconstruct tree from preorder and inorder.
  • Unique node values.
  • Divide and conquer tree reconstruction.

Algorithmic Decision Tree:

  • rootVal = preorder[preStart]; root = new TreeNode(rootVal).
  • inRoot = inMap[rootVal]; numLeft = inRoot - inStart.
  • root.left = build(preStart + 1, preStart + numLeft, inStart, inRoot - 1).
  • root.right = build(preStart + numLeft + 1, preEnd, inRoot + 1, inEnd).

Connected Patterns:

Construct Binary Tree from Inorder and Postorder TraversalConstruct Binary Search Tree from Preorder Traversal

1. Linear Inorder Search Recursion

Intuition

Linear scan to find root index in inorder array. Runs in O(n2) worst case on skewed trees.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If preStart > preEnd return null.
  2. Step 2: rootVal = preorder[preStart].
  3. Step 3: Linearly find inRoot where inorder[inRoot] == rootVal.
  4. Step 4: numLeft = inRoot - inStart.
  5. Step 5: Recurse left and right.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* build(vector<int>& pre, int preS, int preE, vector<int>& in, int inS, int inE) {
10 if (preS > preE || inS > inE) return nullptr;
11 int rootVal = pre[preS];
12 TreeNode* root = new TreeNode(rootVal);
13 int inRoot = inS;
14 while (in[inRoot] != rootVal) inRoot++;
15 int numLeft = inRoot - inS;
16 root->left = build(pre, preS + 1, preS + numLeft, in, inS, inRoot - 1);
17 root->right = build(pre, preS + numLeft + 1, preE, in, inRoot + 1, inE);
18 return root;
19 }
20 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
21 return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n^2) — Linear search inside subarray takes O(n) per level.
  • Space complexity: O(h) — Recursion call stack takes O(h).

2. Subarray Slicing Recursion

Intuition

Pop first element of preorder as rootVal. Slice inorder at root index into leftIn and rightIn. Slice preorder accordingly and recurse.

When to apply: Concise scripting.

Algorithm

  1. Step 1: If inorder is empty return null.
  2. Step 2: rootVal = preorder.shift() / pop(0).
  3. Step 3: idx = inorder.indexOf(rootVal).
  4. Step 4: root.left = buildTree(preorder[0...idx], inorder[0...idx]).
  5. Step 5: root.right = buildTree(preorder[idx...end], inorder[idx+1...end]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7// Array slicing is inefficient in C++; pointer ranges are preferred.
8class Solution {
9public:
10 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
11 if (preorder.empty()) return nullptr;
12 int rootVal = preorder[0];
13 TreeNode* root = new TreeNode(rootVal);
14 auto it = find(inorder.begin(), inorder.end(), rootVal);
15 int idx = distance(inorder.begin(), it);
16 vector<int> leftIn(inorder.begin(), it);
17 vector<int> rightIn(it + 1, inorder.end());
18 vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + idx);
19 vector<int> rightPre(preorder.begin() + 1 + idx, preorder.end());
20 root->left = buildTree(leftPre, leftIn);
21 root->right = buildTree(rightPre, rightIn);
22 return root;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n^2) — Array slicing copies O(n) elements at each level.
  • Space complexity: O(n^2) — Subarray copies consume O(n2) memory.

3. Hash Map for Inorder Indices + Pointer Ranges

Intuition

Store inorder indices in a hash map for O(1) root lookup. Recurse using boundary pointers [preStart, preEnd] and [inStart, inEnd] without array copying.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Map each inorder[i] to i in inMap.
  2. Step 2: Helper build(preStart, preEnd, inStart, inEnd).
  3. Step 3: If preStart > preEnd return null.
  4. Step 4: rootVal = preorder[preStart]; inRoot = inMap[rootVal]; numLeft = inRoot - inStart.
  5. Step 5: root.left = build(preStart + 1, preStart + numLeft, inStart, inRoot - 1).
  6. Step 6: root.right = build(preStart + numLeft + 1, preEnd, inRoot + 1, inEnd). Return root.

Reconstruction Trace for Pre=[3, 9, 20], In=[9, 3, 20]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Root is preorder[0] = 3
Visual state
Values and pointers at this exact step
tree
Root
3 (Root)
L Subtree
9
R Subtree
20

Node order shown; add connections to display explicit tree edges.

root: 3
Check / comparison
Root = 3, numLeft = 1
Decision / next transition
Create root 3. Recurse left and right.
Why this step matters

Step 1: Root is preorder[0] = 3. Inorder index is 1. Nodes before 1 in inorder: [9] (left). Nodes after 1: [20] (right).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 unordered_map<int, int> inMap;
9 TreeNode* build(vector<int>& pre, int preS, int preE, int inS, int inE) {
10 if (preS > preE || inS > inE) return nullptr;
11 int rootVal = pre[preS];
12 TreeNode* root = new TreeNode(rootVal);
13 int inRoot = inMap[rootVal];
14 int numLeft = inRoot - inS;
15 root->left = build(pre, preS + 1, preS + numLeft, inS, inRoot - 1);
16 root->right = build(pre, preS + numLeft + 1, preE, inRoot + 1, inE);
17 return root;
18 }
19public:
20 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
21 for (int i = 0; i < inorder.size(); ++i) inMap[inorder[i]] = i;
22 return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Hash map lookup is O(1). Each node constructed once in O(1).
  • Space complexity: O(n) — Hash map takes O(n) space; call stack takes O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Inorder SearchO(n^2)O(h)Scan for root linearly in inorder array.Subarray scan.
2.Subarray SlicingO(n^2)O(n^2)Slice copies of arrays at each level.Subarray copying.
3.Hash Map + Pointer RangesOptimalO(n)O(n)O(1) root lookup via hash map; pass index boundaries.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: preorder=[1], inorder=[1] -> returns TreeNode(1).
  • Right-skewed tree: left subtree size is 0; handled cleanly when inStart > inRoot - 1.
  • Left-skewed tree: right subtree size is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the use of a hash map to avoid the O(n2) linear scan.
  2. Verify the index math for right preorder start: preStart + numLeft + 1.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the root of the current subtree always at preorder[preStart]?

Back to DSA Sheet