Construct Binary Search Tree from Preorder Traversal

Problem

Given preorder traversal of a BST, reconstruct the tree.

Key insight: Each value must fit within [min, max] bounds. O(n) with bounds or O(n log n) by finding split point.

Solutions

// C — O(n) with bounds
int idx = 0;
TreeNode* build(int* pre, int n, int mn, int mx) {
    if (idx >= n || pre[idx] < mn || pre[idx] > mx) return NULL;
    TreeNode* node = malloc(sizeof(TreeNode));
    node->val = pre[idx++];
    node->left = build(pre, n, mn, node->val);
    node->right = build(pre, n, node->val, mx);
    return node;
}
TreeNode* bstFromPreorder(int* pre, int n) {
    idx = 0;
    return build(pre, n, INT_MIN, INT_MAX);
}

// C++
int idx = 0;
TreeNode* build(vector<int>& pre, int mn, int mx) {
    if (idx >= pre.size() || pre[idx] < mn || pre[idx] > mx) return nullptr;
    auto node = new TreeNode(pre[idx++]);
    node->left = build(pre, mn, node->val);
    node->right = build(pre, node->val, mx);
    return node;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
    idx = 0;
    return build(preorder, INT_MIN, INT_MAX);
}

// Java
int idx = 0;
public TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
TreeNode build(int[] pre, int mn, int mx) {
    if (idx >= pre.length || pre[idx] < mn || pre[idx] > mx) return null;
    TreeNode node = new TreeNode(pre[idx++]);
    node.left = build(pre, mn, node.val);
    node.right = build(pre, node.val, mx);
    return node;
}

// JavaScript
function bstFromPreorder(preorder) {
    let idx = 0;
    function build(mn, mx) {
        if (idx >= preorder.length || preorder[idx] < mn || preorder[idx] > mx) return null;
        const node = new TreeNode(preorder[idx++]);
        node.left = build(mn, node.val);
        node.right = build(node.val, mx);
        return node;
    }
    return build(-Infinity, Infinity);
}

# Python
def bstFromPreorder(preorder):
    idx = [0]
    def build(mn, mx):
        if idx[0] >= len(preorder) or not (mn < preorder[idx[0]] < mx):
            return None
        node = TreeNode(preorder[idx[0]])
        idx[0] += 1
        node.left = build(mn, node.val)
        node.right = build(node.val, mx)
        return node
    return build(float('-inf'), float('inf'))

Complexity

Time: O(n)
Space: O(n)

Key Insight

BST property means each value uniquely belongs to left or right subtree based on bounds. Process preorder left-to-right, narrow bounds each step.