Construct Binary Search Tree from Preorder Traversal

medium tree bst

Problem

Given the preorder traversal of a BST with distinct values, reconstruct the tree.

Inputpreorder = [8,5,1,7,10,12]

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

Recurse with an upper bound; consume values that respect it, recurse into left then right.

preorder (distinct, comma-separated)

def bstFromPreorder(preorder):
    i = 0
    def build(bound):
        nonlocal i
        if i == len(preorder) or preorder[i] > bound: return None
        node = TreeNode(preorder[i]); i += 1
        node.left = build(node.val)
        node.right = build(bound)
        return node
    return build(float('inf'))

function bstFromPreorder(preorder) {
  let i = 0;
  function build(bound) {
    if (i === preorder.length || preorder[i] > bound) return null;
    const node = { val: preorder[i++], left: null, right: null };
    node.left = build(node.val);
    node.right = build(bound);
    return node;
  }
  return build(Infinity);
}

class Solution {
    int i = 0; int[] pre;
    public TreeNode bstFromPreorder(int[] preorder) { pre = preorder; return build(Integer.MAX_VALUE); }
    TreeNode build(int bound) {
        if (i == pre.length || pre[i] > bound) return null;
        TreeNode node = new TreeNode(pre[i++]);
        node.left = build(node.val);
        node.right = build(bound);
        return node;
    }
}

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

Explanation

A preorder list of a BST always starts with the root, then the whole left subtree, then the whole right subtree. The clever trick here is to rebuild the tree in a single left-to-right pass using an upper bound to decide where each value belongs.

We keep a moving pointer i into preorder and a helper build(bound). A value can join the current subtree only if it is less than the bound. If the next value preorder[i] > bound (or we ran out), there is nothing to build here, so we return None.

Otherwise we take the value as a new node, advance i, and recurse twice. The left child is built with the bound set to this node's own value (left items must be smaller). The right child keeps the inherited bound.

Example: preorder = [8, 5, 1, 7, 10, 12]. Root 8 (bound ∞). Left of 8 uses bound 8: take 5, then its left uses bound 5 (take 1), its right uses bound 8 (take 7). Back at 8, the right side uses bound ∞: take 10, then 12 on its right.

Because each value is consumed exactly once and the bound tells us instantly whether it fits, the whole tree is built in one linear sweep.

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