Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Construct Binary Search Tree from Preorder Traversal

MEDIUMProblemSolveExternal Links

Description

You are given an array of integers preorder, which represents the preorder traversal of a Binary Search Tree (BST). Your task is to construct the BST and return its root node.

In a preorder traversal, we visit the current node first, then recursively traverse the entire left subtree, followed by the entire right subtree. In a BST, for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater.

It is guaranteed that a valid BST can always be constructed from the given preorder traversal. All values in the input are unique.

Examples

Example 1

Input: preorder = [8, 5, 1, 7, 10, 12]

Output: [8, 5, 10, 1, 7, null, 12]

Explanation: The preorder array [8, 5, 1, 7, 10, 12] describes a BST where 8 is visited first (the root), then the left subtree [5, 1, 7] is traversed in preorder, followed by the right subtree [10, 12].

The resulting BST:

       8
      / \
     5   10
    / \    \
   1   7   12

Node 8 is the root. Its left subtree contains 5 (with children 1 and 7, both correctly placed since 1 < 5 < 7). Its right subtree contains 10 (with right child 12, since 12 > 10).

Example 2

Input: preorder = [1, 3]

Output: [1, null, 3]

Explanation: With only two elements, 1 is the root (visited first in preorder). Since 3 > 1, it becomes the right child of 1. The left child is null because no value in the preorder array is less than 1.

Constraints

  • 1 ≤ preorder.length ≤ 100
  • 1 ≤ preorder[i] ≤ 1000
  • All values of preorder are unique

Editorial

Brute Force

Intuition

The most straightforward approach is to build the BST by inserting elements one at a time, just like you would manually construct a BST from a list of values.

Preorder traversal visits the root first, then the left subtree, then the right subtree. The first element in the preorder array is always the root. Each subsequent element gets inserted into the growing BST following the standard insertion rule: if the new value is less than the current node, go left; if greater, go right; when you reach an empty spot, place the new node there.

Think of it like building a family tree. The first person becomes the founder (root). Each new person joins the family by comparing themselves with existing members, starting from the founder, and finding their correct position.

Since preorder preserves the parent-before-children ordering, inserting elements in preorder order naturally reconstructs the original BST structure.

Step-by-Step Explanation

Let's trace through Example 1 with preorder = [8, 5, 1, 7, 10, 12]:

Step 1: The first element is 8. Create the root node with value 8. The tree has one node.

Step 2: Insert 5. Start at root 8. Since 5 < 8, go left. Left is empty — insert 5 as the left child of 8.

Step 3: Insert 1. Start at root 8. 1 < 8 → go left to node 5. 1 < 5 → go left. Left is empty — insert 1 as the left child of 5.

Step 4: Insert 7. Start at root 8. 7 < 8 → go left to node 5. 7 > 5 → go right. Right is empty — insert 7 as the right child of 5.

Step 5: Insert 10. Start at root 8. 10 > 8 → go right. Right is empty — insert 10 as the right child of 8.

Step 6: Insert 12. Start at root 8. 12 > 8 → go right to node 10. 12 > 10 → go right. Right is empty — insert 12 as the right child of 10.

Step 7: All 6 elements inserted. The BST is fully constructed.

Sequential BST Insertion from Preorder Array — Watch how each element from the preorder array is inserted into the BST by following the BST property: values less than the current node go left, greater values go right.

Algorithm

  1. Create the root node from preorder[0]
  2. For each remaining element in the preorder array:
    • Start at the root
    • Compare the value with the current node
    • If smaller, move to the left child; if larger, move to the right child
    • When an empty position is reached, insert the new node there
  3. Return the root

Code

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = nullptr;
        for (int val : preorder) {
            root = insert(root, val);
        }
        return root;
    }

    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val)
            node->left = insert(node->left, val);
        else
            node->right = insert(node->right, val);
        return node;
    }
};
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        root = None

        def insert(node, val):
            if not node:
                return TreeNode(val)
            if val < node.val:
                node.left = insert(node.left, val)
            else:
                node.right = insert(node.right, val)
            return node

        for val in preorder:
            root = insert(root, val)
        return root
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = null;
        for (int val : preorder) {
            root = insert(root, val);
        }
        return root;
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val)
            node.left = insert(node.left, val);
        else
            node.right = insert(node.right, val);
        return node;
    }
}

Complexity Analysis

Time Complexity: O(n × h) where n is the number of elements and h is the tree height

Each of the n elements is inserted by traversing from the root to an empty position, which takes O(h) time. For a balanced BST, h ≈ log n, giving O(n log n) total. However, if the preorder array is sorted (e.g., [1, 2, 3, 4, 5]), the BST degenerates into a chain where h = n, giving O(n²) worst case.

Space Complexity: O(n)

The tree itself uses O(n) space for n nodes. The recursion stack during insertion uses O(h) space. For a balanced tree h = O(log n); for a skewed tree h = O(n).

Why This Approach Is Not Efficient

The sequential insertion approach can degrade to O(n²) when the input produces a skewed tree. For a sorted preorder like [1, 2, 3, ..., n], each new element is inserted at the end of a growing chain, requiring O(k) comparisons for the k-th element. The total work becomes 1 + 2 + 3 + ... + (n-1) = O(n²).

More fundamentally, this approach ignores the structural information encoded in the preorder sequence. It treats the input as an arbitrary list of values and inserts them blindly, not recognizing which elements belong to the left subtree versus the right subtree.

The preorder traversal has a powerful property: the first element is the root, all subsequent elements smaller than the root belong to the left subtree, and all elements greater belong to the right. We can exploit this structure directly using a divide-and-conquer strategy.

Better Approach - Recursive Partitioning

Intuition

Instead of inserting elements blindly, we can use the structure of preorder traversal directly. In any preorder traversal of a BST:

  1. The first element is always the root.
  2. All subsequent elements that are less than the root form the left subtree's preorder.
  3. All subsequent elements that are greater than the root form the right subtree's preorder.
  4. The left subtree elements always appear before the right subtree elements.

So we can find the partition point — the first index where the value exceeds the root — and recursively build the left subtree from elements before the partition, and the right subtree from elements after it.

Think of it like sorting mail at a post office. The root value is the dividing threshold. Every letter with a number below the threshold goes into the 'left' bin, and every letter with a number above goes into the 'right' bin. Then you repeat the same sorting process within each bin until every letter has been placed.

Step-by-Step Explanation

Let's trace through Example 1 with preorder = [8, 5, 1, 7, 10, 12]:

Step 1: Root = preorder[0] = 8. Scan from index 1 to find the first value greater than 8. Check: 5 (≤ 8), 1 (≤ 8), 7 (≤ 8), 10 (> 8). Partition found at index 4.

Step 2: Split: left subtree from indices 1-3 → [5, 1, 7]. Right subtree from indices 4-5 → [10, 12].

Step 3: Recurse on left [5, 1, 7]. Root = 5. Scan for first value > 5: 1 (≤ 5), 7 (> 5). Partition at relative index 2. Left = [1], Right = [7].

Step 4: [1] is a single element → leaf node. [7] is a single element → leaf node. Left subtree of 8 is complete: 5 with children 1 and 7.

Step 5: Recurse on right [10, 12]. Root = 10. Scan for first value > 10: 12 (> 10). Partition: left = [], right = [12].

Step 6: Left of 10 is empty. [12] is a single element → leaf node. Right subtree of 8 is complete: 10 with right child 12.

Step 7: Construction complete. Result: 8(5(1,7), 10(null,12)).

Recursive Partitioning — Divide and Conquer on Preorder Array — Watch how the preorder array is recursively split into root, left subtree, and right subtree at each level by finding the first element greater than the current root.

Algorithm

  1. Define a recursive function build(preorder, start, end) that constructs a BST from preorder[start..end]
  2. Base case: if start > end, return null
  3. Create a root node with value preorder[start]
  4. Find the partition index — the first index in [start+1, end] where preorder[index] > preorder[start]
  5. Recursively build the left subtree: build(preorder, start+1, partition-1)
  6. Recursively build the right subtree: build(preorder, partition, end)
  7. Return the root

Code

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return build(preorder, 0, preorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int start, int end) {
        if (start > end) return nullptr;
        TreeNode* root = new TreeNode(preorder[start]);
        int partition = start + 1;
        while (partition <= end && preorder[partition] < preorder[start]) {
            partition++;
        }
        root->left = build(preorder, start + 1, partition - 1);
        root->right = build(preorder, partition, end);
        return root;
    }
};
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        def build(start, end):
            if start > end:
                return None
            root = TreeNode(preorder[start])
            partition = start + 1
            while partition <= end and preorder[partition] < preorder[start]:
                partition += 1
            root.left = build(start + 1, partition - 1)
            root.right = build(partition, end)
            return root

        return build(0, len(preorder) - 1)
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return build(preorder, 0, preorder.length - 1);
    }

    private TreeNode build(int[] preorder, int start, int end) {
        if (start > end) return null;
        TreeNode root = new TreeNode(preorder[start]);
        int partition = start + 1;
        while (partition <= end && preorder[partition] < preorder[start]) {
            partition++;
        }
        root.left = build(preorder, start + 1, partition - 1);
        root.right = build(preorder, partition, end);
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n²) worst case, O(n log n) average

At each recursive call, we scan the subarray to find the partition point, which takes O(k) time where k is the subarray size. For a balanced BST, the total scanning work across all levels is O(n log n) — each level scans O(n) elements total, and there are O(log n) levels. For a skewed tree (e.g., sorted preorder), scanning at each level touches nearly the entire remaining array, giving O(n²).

Space Complexity: O(n)

The recursion stack depth equals the tree height: O(log n) for balanced, O(n) for skewed. The tree itself stores n nodes.

Why This Approach Is Not Efficient

The recursive partitioning approach correctly exploits the preorder structure, but it still has a hidden cost: at each recursive call, we scan the subarray to find the partition point. This scan takes O(k) time where k is the subarray size.

For a balanced tree, the total scanning work across all levels is O(n log n). But for a skewed tree (e.g., preorder = [1, 2, 3, 4, 5]), the scan at each level touches nearly the entire remaining array, leading to O(n²) total.

The key insight for improvement is this: instead of explicitly scanning for the partition point, we can implicitly determine it using a bound parameter. As we process elements left to right with a shared index, a value that exceeds the current bound tells us the left subtree is complete — no scanning needed. This eliminates the O(k) partition scan at every level, reducing total time from O(n²) to O(n).

Optimal Approach - Recursive Construction with Upper Bound

Intuition

We can construct the BST in a single left-to-right pass through the preorder array by maintaining an upper bound for valid node values.

The key idea is elegant: we process preorder elements sequentially using a shared index counter. Each recursive call receives a bound parameter — the maximum value a node can have in the current subtree:

  • If the current element exceeds the bound, this subtree is empty — return null immediately.
  • Otherwise, create a node with the current element and advance the shared index.
  • Build the left subtree with bound = node.val (left children must be strictly less than the parent).
  • Build the right subtree with bound = original_bound (right children must respect the ancestor's constraint).

The bound naturally prevents elements from the wrong subtree from being consumed. When building the left subtree of node 8, the bound is 8. When we encounter 10 (which exceeds 8), we know the left subtree is done — without any scanning.

Think of it as a conveyor belt of packages (the preorder array) being sorted into shelves (tree nodes). Each shelf has a weight limit (the bound). You take packages off the belt one by one. If a package is too heavy for the current shelf, you close that shelf and move up to the parent shelf, which has a higher limit.

Diagram showing how preorder array [8,5,1,7,10,12] maps to BST structure with root, left subtree, and right subtree labeled
Diagram showing how preorder array [8,5,1,7,10,12] maps to BST structure with root, left subtree, and right subtree labeled

Step-by-Step Explanation

Let's trace through Example 1 with preorder = [8, 5, 1, 7, 10, 12]:

Step 1: Call build(bound=∞). preorder[0] = 8. Since 8 ≤ ∞, create root node 8. Advance index to 1.

Step 2: Build left subtree of 8: call build(bound=8). preorder[1] = 5. Since 5 ≤ 8, create node 5. Advance index to 2.

Step 3: Build left of 5: call build(bound=5). preorder[2] = 1. Since 1 ≤ 5, create node 1. Advance index to 3.

Step 4: Build left of 1: call build(bound=1). preorder[3] = 7. But 7 > 1 — bound exceeded! Return null. Build right of 1: call build(bound=5). 7 > 5 — bound exceeded again! Return null. Node 1 is a leaf.

Step 5: Back to node 5. Build right of 5: call build(bound=8). preorder[3] = 7. Since 7 ≤ 8, create node 7. Advance index to 4. Build children of 7: left build(bound=7) → preorder[4]=10 > 7 → null. Right build(bound=8) → 10 > 8 → null. Node 7 is a leaf.

Step 6: Back to root 8. Build right subtree: call build(bound=∞). preorder[4] = 10. Since 10 ≤ ∞, create node 10. Advance index to 5.

Step 7: Build left of 10: call build(bound=10). preorder[5] = 12. But 12 > 10 → null. Build right of 10: call build(bound=∞). 12 ≤ ∞ → create node 12. Advance index to 6.

Step 8: Index 6 = array length. All elements consumed. BST construction complete!

Optimal Construction — Upper Bound Controls Subtree Boundaries — Watch how a shared index advances through the preorder array while the upper bound parameter automatically determines when each subtree is complete — no scanning needed.

Algorithm

  1. Initialize a shared index variable idx = 0
  2. Define recursive function build(bound):
    • If idx >= n or preorder[idx] > bound, return null (subtree is empty)
    • Create a node with value preorder[idx] and increment idx
    • Build left subtree: node.left = build(node.val) — left children must be less than the current node
    • Build right subtree: node.right = build(bound) — right children must respect the ancestor's upper bound
    • Return the node
  3. Call build(∞) and return the result

Code

class Solution {
public:
    int idx = 0;

    TreeNode* bstFromPreorder(vector<int>& preorder) {
        idx = 0;
        return build(preorder, INT_MAX);
    }

    TreeNode* build(vector<int>& preorder, int bound) {
        if (idx >= preorder.size() || preorder[idx] > bound) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[idx++]);
        root->left = build(preorder, root->val);
        root->right = build(preorder, bound);
        return root;
    }
};
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        self.idx = 0

        def build(bound):
            if self.idx >= len(preorder) or preorder[self.idx] > bound:
                return None
            root = TreeNode(preorder[self.idx])
            self.idx += 1
            root.left = build(root.val)
            root.right = build(bound)
            return root

        return build(float('inf'))
class Solution {
    private int idx = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        idx = 0;
        return build(preorder, Integer.MAX_VALUE);
    }

    private TreeNode build(int[] preorder, int bound) {
        if (idx >= preorder.length || preorder[idx] > bound) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[idx++]);
        root.left = build(preorder, root.val);
        root.right = build(preorder, bound);
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each element in the preorder array is processed exactly once. The shared index advances from 0 to n-1, and each increment corresponds to creating one node. No element is ever revisited or scanned over multiple times. The bound checks are O(1) per call. Total: O(n).

Space Complexity: O(h) where h is the height of the BST

The recursion stack depth equals the tree height. For a balanced BST, h = O(log n). For a completely skewed tree, h = O(n). The tree itself uses O(n) space for the n nodes, but that is the required output space, not auxiliary space. The auxiliary space is O(h) for the recursion stack.