Construct Binary Search Tree from Preorder Traversal (LeetCode -1008)

Question: Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., 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 binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Example 1:

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

Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

Constraints:

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

Solution : Approach, Complexity, Code, Dry Run

Approach

Note: This approach is different from the standard upper bound + preorder index solution commonly used for this problem. Instead, it uses the Next Greater Index (NGI) computed via a monotonic decreasing stack to determine the boundary between the left and right subtrees. While less common, it still achieves O(n) time complexity.

The first element of a preorder traversal is always the root of the BST. All consecutive elements smaller than the root belong to its left subtree, while the first greater element marks the beginning of the right subtree.

A naive solution searches for this split point during every recursive call, leading to O(n²) time in the worst case.

To optimize this, we first preprocess the preorder array using a monotonic decreasing stack to compute the Next Greater Index (NGI) for every element. The NGI directly gives the boundary between the left and right subtrees, allowing each recursive call to determine the split point in O(1) time.

During recursion:

• preorder[l] is the root.
• break_point[l] stores the index of the first greater element (or n if none exists).
• The left subtree is constructed from (l + 1, mid - 1).
• The right subtree is constructed from (mid, r).

Since each element is processed only once during preprocessing and once during recursion, the overall algorithm runs in linear time.

Complexity Analysis

• Time Complexity: O(n)
• O(n) to compute the Next Greater Index using a monotonic stack.
• O(n) to recursively construct the BST.
• Space Complexity: O(n)
• O(n) for the break_point array and monotonic stack.
• Recursive call stack uses O(h) space, where h is the height of the BST (worst case O(n)).

Code :

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        n = len(preorder)

        # break_point[i] = index of first greater element to the right
        break_point = [n] * n
        stack = []

        for i in range(n):
            while stack and preorder[stack[-1]] < preorder[i]:
                break_point[stack.pop()] = i
            stack.append(i)

        def build(l, r):
            if l > r:
                return None

            root = TreeNode(preorder[l])

            mid = break_point[l]

            root.left = build(l + 1, mid - 1)
            root.right = build(mid, r)

            return root

        return build(0, n - 1)

Dry Run Example

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

1. Preprocessing (Next Greater Index)

The stack keeps track of indices of elements we haven’t found a “greater” neighbor for yet. When we encounter a value larger than the top of the stack, that value is the “Next Greater” for the stack-top element.

• i=0 (8): Stack: [0]
• i=1 (5): 5 < 8. Stack: [0, 1]
• i=2 (1): 1 < 5. Stack: [0, 1, 2]
• i=3 (7): 7 > 1 (pop 2, break_point[2]=3), 7 > 5 (pop 1, break_point[1]=3). Stack: [0, 3]
• i=4 (10): 10 > 7 (pop 3, break_point[3]=4), 10 > 8 (pop 0, break_point[0]=4). Stack: [4]
• i=5 (12): 12 > 10 (pop 4, break_point[4]=5). Stack: [5]

Resulting break_point array: [4, 3, 3, 4, 5, 6]

2. Recursive Construction , preorder= [8, 5, 1, 7, 10, 12]

The break_point allows us to instantly find the mid (the start of the right subtree), turning the construction into a clean partition:

• **build(0, 5)**: Root is 8. mid = break_point[0] = 4. Left: build(1, 3) (Values [5, 1, 7]) Right: build(4, 5) (Values [10, 12])
• **build(1, 3)**: Root is 5. mid = break_point[1] = 3. Left: build(2, 2) (Value 1) Right: build(3, 3) (Value 7)
• **build(4, 5)**: Root is 10. mid = break_point[4] = 5. Left: build(5, 4) (None) Right: build(5, 5) (Value 12)

By using these boundaries, the algorithm avoids the O(n²) search for the split point, ensuring every node is touched exactly once for a clean O(n) result.