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.
def bstFromPreorder(preorder):
def build(minVal, maxVal):
nonlocal idx
if idx >= len(preorder):
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(float('-inf'), float('inf'))
Time: . Each node is visited once. The bounds ensure BST property is maintained.