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: . Each node is visited once. The bounds ensure BST property is maintained.