DSA Tracker

Visualize

Construct Binary Search Tree from Preorder Traversal

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

time O(n)space O(h)

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.

Details

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].

Problem:Construct Binary Search Tree from Preorder TraversalMedium

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

step 1 / 13

8
≤∞

Call stack

build(≤∞, id=t8)

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

Every step in words

Show all 13 steps
  1. preorder[0] = 8 has no bound yet, so it becomes the root.
  2. preorder[1] = 5 fits under the bound ≤8 inherited from 8, so it becomes 8's left child.
  3. preorder[2] = 1 fits under the bound ≤5 inherited from 5, so it becomes 5's left child.
  4. Both of 1's child calls hit the base case immediately (7 exceeds every bound in play here), so 1 is a leaf. build(≤5) returns 1.
  5. preorder[3] = 7 fits under the bound ≤8 inherited from 5, so it becomes 5's right child.
  6. Both of 7's child calls hit the base case immediately (10 exceeds every bound in play here), so 7 is a leaf. build(≤8) returns 7.
  7. 5's children are attached (left = 1, right = 7), so build(≤8) returns 5.
  8. preorder[4] = 10 fits under the bound ≤∞ inherited from 8, so it becomes 8's right child.
  9. preorder[5] = 12 fits under the bound ≤∞ inherited from 10, so it becomes 10's right child.
  10. Both of 12's child calls hit the base case immediately (preorder is exhausted), so 12 is a leaf. build(≤∞) returns 12.
  11. 10's children are attached (left = null, right = 12), so build(≤∞) returns 10.
  12. 8's children are attached (left = 5, right = 10), so build(≤∞) returns 8.
  13. Done: level order is [8, 5, 10, 1, 7, null, 12], matching the expected BST. Every preorder value was consumed exactly once, each in O(1) amortized work, so the whole build costs O(n).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Construct Binary Search Tree from Preorder Traversal in the editorAll BST problemsBack to roadmap