Pattern visualizer

Construct BST from Preorder

In preorder, the first element is always the current subtree's root. Everything after it that is smaller belongs to the left subtree, everything larger to the right — so instead of searching for that split point, carry an upper bound down through the recursion: the next preorder value becomes a node here only if it is still under the bound this call inherited. The left child then bounds by the node's own value; the right child keeps the same bound, since it can still absorb anything up to that ancestor's limit. Animated on: preorder = [8, 5, 1, 7, 10, 12] — this is the preorder traversal of a BST. Rebuild the tree. Expected: [8, 5, 10, 1, 7, null, 12]..

A value becomes a node only if it fits under the bound inherited from above

time O(n)space O(h)step 1 / 13

≤∞

Call stack

build(≤∞, id=t8)

line 7

preorder[0] = 8 has no bound yet, so it becomes the root.

Pseudocode

1FUNCTION buildBst(preorder):
2  idx <- 0
3  RETURN build(+INFINITY)
4FUNCTION build(bound):
5  IF idx = LENGTH(preorder) OR preorder[idx] > bound:
6    RETURN null
7  val <- preorder[idx]; idx <- idx + 1
8  node <- NEW NODE(val)
9  node.left <- build(val)
10  node.right <- build(bound)
11  RETURN node

← / → step · space play · Home restart

Where to practice BST

Practice BST problems All BST problems Back to roadmap