Log inSign up
mediumLeetCodeNot Started

Construct BST from Preorder Traversal

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

BST
Solve on LeetCode
Lesson

Problem Statement

Given an array of integers preorder, which represents the preorder traversal of a BST (binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A preorder traversal displays the values of the node first, then traverses left, then traverses right.

Constraints:

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 1000
  • All the values of preorder are unique.

What You'll Learn

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

  • Construct a valid BST from preorder data in optimal O(N) single-pass time.
  • Understand why an upper-bound parameter alone is sufficient for BST reconstruction.
  • Compare recursive upper-bound parsing with monotonic stack-based construction.

Pattern Recognition Trigger

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

Signals to Look For:

  • Construct BST from preorder array.
  • O(N) linear construction requirement.
  • Root-first element layout.

Algorithmic Decision Tree:

  • Maintain running index and upper bound: if (nums[idx] > bound) return null.
  • Left child bound is curr.val; right child bound is inherited bound.

Connected Patterns:

Serialize and Deserialize BSTValidate Binary Search TreeConstruct Binary Tree from Preorder and Inorder Traversal

1. Sequential Insertion

Intuition

Initialize root with preorder[0]. For each subsequent element in preorder, call standard BST insert(root, val). In the worst case (already sorted array producing a skewed tree), each insertion takes O(N), yielding O(N2) total time.

When to apply: Basic baseline when constraints are very small.

Algorithm

  1. Step 1: Set root = TreeNode(preorder[0]).
  2. Step 2: Loop i from 1 to N - 1: insert(root, preorder[i]).
  3. Step 3: Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 TreeNode* insert(TreeNode* root, int val) {
13 if (!root) return new TreeNode(val);
14 if (val < root->val) root->left = insert(root->left, val);
15 else root->right = insert(root->right, val);
16 return root;
17 }
18public:
19 TreeNode* bstFromPreorder(vector<int>& preorder) {
20 if (preorder.empty()) return nullptr;
21 TreeNode* root = new TreeNode(preorder[0]);
22 for (size_t i = 1; i < preorder.size(); i++) insert(root, preorder[i]);
23 return root;
24 }
25};
26
27int main() {
28 vector<int> pre = {8, 5, 1, 7, 10, 12};
29 Solution sol;
30 TreeNode* root = sol.bstFromPreorder(pre);
31 cout << "Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2) worst-case, O(N log N) average
  • Space complexity: O(H) recursion stack

2. Sort to Inorder + Two Pointers Build

Intuition

Clone and sort preorder array to obtain the inorder traversal. Build a hash map of value to index in inorder array. Use standard divide and conquer: root is preorder[preStart], look up its index in inorder map, split left and right subtrees.

When to apply: When reducing to the standard 'Construct Binary Tree from Preorder and Inorder Traversal' problem.

Algorithm

  1. Step 1: inorder = sort(preorder.clone()).
  2. Step 2: Map each value to its index in inorder.
  3. Step 3: Recursively construct tree using preorder and inorder intervals.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_map>
5using namespace std;
6
7struct TreeNode {
8 int val;
9 TreeNode *left, *right;
10 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11};
12
13class Solution {
14 unordered_map<int, int> inMap;
15 TreeNode* build(const vector<int>& pre, int pStart, int pEnd, const vector<int>& in, int iStart, int iEnd) {
16 if (pStart > pEnd || iStart > iEnd) return nullptr;
17 TreeNode* root = new TreeNode(pre[pStart]);
18 int inRoot = inMap[root->val];
19 int numsLeft = inRoot - iStart;
20 root->left = build(pre, pStart + 1, pStart + numsLeft, in, iStart, inRoot - 1);
21 root->right = build(pre, pStart + numsLeft + 1, pEnd, in, inRoot + 1, iEnd);
22 return root;
23 }
24public:
25 TreeNode* bstFromPreorder(vector<int>& preorder) {
26 vector<int> inorder = preorder;
27 sort(inorder.begin(), inorder.end());
28 for (int i = 0; i < inorder.size(); i++) inMap[inorder[i]] = i;
29 return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
30 }
31};
32
33int main() {
34 vector<int> pre = {8, 5, 1, 7, 10, 12};
35 Solution sol;
36 TreeNode* root = sol.bstFromPreorder(pre);
37 cout << "Optimal Root: " << root->val << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

3. Upper-Bound Linear Construction (O(N) Single Pass)

Intuition

Track a shared index idx = 0 in preorder array. Define build(bound): if idx >= length or preorder[idx] > bound, return null. Otherwise, consume val = preorder[idx++]. Construct node with val. Recursively build left child with bound val (since left child must be < val), then recursively build right child with bound bound. Returns in strictly O(N) time.

When to apply: The industry standard Gold Standard solution.

Algorithm

  1. Step 1: Track shared pointer idx = 0.
  2. Step 2: Helper build(bound): if idx == length or preorder[idx] > bound, return null.
  3. Step 3: root = TreeNode(preorder[idx++]).
  4. Step 4: root.left = build(root.val) (left values must be < root.val).
  5. Step 5: root.right = build(bound) (right values can be up to bound).
  6. Step 6: Return root.

BST Preorder Build Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Root 8 initialized with upper bound infinity
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Root 8 initialized with upper bound infinity.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left, *right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 TreeNode* build(const vector<int>& preorder, int& idx, int bound) {
14 if (idx >= preorder.size() || preorder[idx] > bound) return nullptr;
15 TreeNode* root = new TreeNode(preorder[idx++]);
16 root->left = build(preorder, idx, root->val);
17 root->right = build(preorder, idx, bound);
18 return root;
19 }
20public:
21 TreeNode* bstFromPreorder(vector<int>& preorder) {
22 int idx = 0;
23 return build(preorder, idx, INT_MAX);
24 }
25};
26
27int main() {
28 vector<int> pre = {8, 5, 1, 7, 10, 12};
29 Solution sol;
30 TreeNode* root = sol.bstFromPreorder(pre);
31 cout << "Optimal Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sequential InsertionO(N^2) worstO(H)Insert one by one.Deep traversal per node.
2.Sort to Inorder + MapO(N log N)O(N)Derive inorder by sorting.Sorting overhead.
3.Upper-Bound Linear (Optimal)OptimalO(N)O(H)Single pass bounded recursion.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Linear search for split point

Searching for the first element greater than root in O(N) gives O(N2) worst-case time. Use upper-bound recursion for O(N).

Passing index by value instead of by reference

If the pointer idx is not shared across recursive calls, the algorithm processes duplicate nodes.

Forgetting boundary check against array length

Accessing preorder[idx] when idx >= length throws an IndexOutOfBounds exception.

Crucial Edge Cases to Validate:

  • Single element array `[1]` — Correctly returns a 1-node tree.
  • Strictly descending array `[5, 4, 3, 2, 1]` — Builds a strictly left-skewed tree.
  • Strictly ascending array `[1, 2, 3, 4, 5]` — Builds a strictly right-skewed tree.
  • Balanced array `[4, 2, 1, 3, 6, 5, 7]` — Builds a complete balanced BST.

Interview Tips & Best Practices

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

  1. Emphasize the upper-bound insight: 'Preorder root is first, left child bound is root.val, right child bound is current bound.'
  2. Highlight that this problem is the inverse of 'Validate Binary Search Tree'.
  3. Contrast the O(N) single-pass with the naive O(N log N) sort-and-map approach.

Quick Comprehension Check

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

1.Why is an UPPER BOUND parameter alone sufficient to reconstruct a BST from preorder, without needing a lower bound?

2.What is the time complexity of the upper-bound approach?

3.How does the Monotonic Stack approach reconstruct the tree iteratively?

Back to DSA Sheet