BST from Preorder

Given preorder traversal of a BST, reconstruct the tree. Unlike general binary trees, preorder alone is enough for BST because the BST property constrains structure.

function bstFromPreorder(preorder):
    function build(minVal, maxVal):
        if idx >= preorder.length:
            return null
        val = preorder[idx]
        if val < minVal or val > maxVal:
            return null
        idx += 1
        node = TreeNode(val)
        node.left = build(minVal, val)
        node.right = build(val, maxVal)
        return node

    idx = 0
    return build(-INFINITY, INFINITY)

Time: $O(n)$. Each node is visited once. The bounds ensure BST property is maintained.