AlgoScope

Build and Validate a BST

algorithmintermediateTime O(n)Space O(h)

Sorted input inserted in order makes a chain, so build from the middle out instead. And checking a tree means checking every node against a window inherited from all its ancestors, not just its parent.

Rebuild the search tree whose preorder is 50, 30, 20, 40, 70, 60, 80. Preorder writes a node before its subtrees, so each value is a child of something already placed: smaller than the most recent node means its left child; larger means it belongs to the right of the nearest earlier node that is still bigger than it. The stack holds the path of nodes whose right side is open.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. The stack is 50 on top and the next value is 30. Where does 30 go?

    • Left child of 50
    • Right child of 50

    Answer: Left child of 50. Smaller than the top means left child of the top.

  2. The stack is 30 on top and the next value is 20. Where does 20 go?

    • Left child of 30
    • Right child of 30

    Answer: Left child of 30. Smaller than the top means left child of the top.

  3. The stack is 20 on top and the next value is 40. Where does 40 go?

    • Right child of 30
    • Left child of 20
    • Right child of 20

    Answer: Right child of 30. Pop every stack node smaller than 40; it is the right child of the last one popped.

  4. The stack is 40 on top and the next value is 70. Where does 70 go?

    • Right child of 50
    • Left child of 40
    • Right child of 40

    Answer: Right child of 50. Pop every stack node smaller than 70; it is the right child of the last one popped.

  5. The stack is 70 on top and the next value is 60. Where does 60 go?

    • Left child of 70
    • Right child of 70

    Answer: Left child of 70. Smaller than the top means left child of the top.

  6. The stack is 60 on top and the next value is 80. Where does 80 go?

    • Right child of 70
    • Left child of 60
    • Right child of 60

    Answer: Right child of 70. Pop every stack node smaller than 80; it is the right child of the last one popped.

How it runs, step by step

  1. Rebuild the search tree whose preorder is 50, 30, 20, 40, 70, 60, 80. Preorder writes a node before its subtrees, so each value is a child of something already placed: smaller than the most recent node means its left child; larger means it belongs to the right of the nearest earlier node that is still bigger than it. The stack holds the path of nodes whose right side is open.

    Rebuilding a BST from preorder 50, 30, 20, 40, 70, 60, 80.

  2. The first value, 50, is the root. Push it: its right side is open.

    50 is the root.

  3. Next is 30. It is smaller than 50 on top of the stack, so it is the left child of 50. Push it.

    30 is the left child of 50.

  4. Next is 20. It is smaller than 30 on top of the stack, so it is the left child of 30. Push it.

    20 is the left child of 30.

  5. Next is 40. It is larger than 20, 30, which are popped: their right sides are now spoken for. 40 becomes the right child of 30, the last one popped. Push it.

    40 is the right child of 30.

  6. Next is 70. It is larger than 40, 50, which are popped: their right sides are now spoken for. 70 becomes the right child of 50, the last one popped. Push it.

    70 is the right child of 50.

  7. Next is 60. It is smaller than 70 on top of the stack, so it is the left child of 70. Push it.

    60 is the left child of 70.

  8. Next is 80. It is larger than 60, 70, which are popped: their right sides are now spoken for. 80 becomes the right child of 70, the last one popped. Push it.

    80 is the right child of 70.

  9. All 7 values placed, height 3. Each value was pushed once and popped at most once, so the rebuild is O(n). Reading the tree back in preorder gives 50, 30, 20, 40, 70, 60, 80 again.

    Tree rebuilt with height 3.

Remember

  • The middle of a sorted range is the root of a balanced subtree. Recurse on both halves.
  • A node can be on the right side of its parent and still on the wrong side of a grandparent.
  • Pass a (low, high) window down. Left children tighten high, right children tighten low.

Topics covered

Related

Where this is used

DatabasesBuilding a database index in bulk

PostgreSQL does not build a B-tree index with n inserts. CREATE INDEX sorts every key first, then writes the leaf pages in order and fills the levels above them as it goes, so placing an entry costs no search and the leaf pages come out packed to the index fillfactor rather than left partly empty by page splits. The B-tree stays balanced either way - what bulk loading avoids is the root-to-leaf descent per key and the loose packing, not a collapse into a chain.

Standard librariesDeserializing a java.util.TreeMap

A serialized TreeMap stores its entries in ascending key order and nothing about its shape. On the way back in, readObject calls the private buildFromSorted, which takes the middle entry of the range as the subtree root and recurses on both halves - fromSorted with one extra step that colours the deepest level red so the red-black invariant holds. The TreeMap(SortedMap) constructor takes the same path, which is why copying a sorted map is linear rather than n insertions with rotations.

OperationsChecking an index for corruption

PostgreSQL's amcheck extension verifies a live B-tree index, and its stricter bt_index_parent_check descends carrying the key bounds that each parent downlink implies. That is the (low, high) window at page scale: a page whose own keys are in perfect order can still hold keys that belong on the other side of an ancestor, and only a check that inherits bounds from above will see it.

Scientific computingNearest-neighbour search over points

scipy.spatial.KDTree splits a point set recursively, one axis per level, and the split value becomes that subtree's root - fromSorted generalised past a single sorted line. Splitting near the middle of the points is the whole game: it is what holds the depth near log n, and a build that split on whichever point happened to arrive first would produce the same chain that sorted inserts produce here.

Why it works this way

Why is building from a sorted array O(n) and not O(n log n)?

fromSorted never searches. The index arithmetic already says where every value belongs, so each call does constant work and the recurrence is T(n) = 2T(n/2) + O(1), which is linear. Inserting the same n values one at a time costs O(n log n) even on a tree that stays balanced, because every insert walks down from the root again.

Int.MIN_VALUE and Int.MAX_VALUE are not safe starting bounds

Calling isBst(root, Int.MIN_VALUE, Int.MAX_VALUE) looks harmless until a node actually holds one of those two values: the check n.key <= low then fires on a perfectly valid tree. Use bounds that cannot collide with a key - nullable low and high that are skipped when absent, or Long bounds around Int keys. Strictness matters in the ordinary case too: both comparisons reject an equal key, so this validator calls any tree holding a duplicate invalid, and a tree that does store duplicates has to loosen exactly one side and then insert on that same side forever.

Why preorder can rebuild the tree when inorder cannot

The inorder walk of any BST is the keys in sorted order, so every BST over the same keys produces the identical inorder sequence - it carries no shape at all. Preorder names the root first, and the BST property then splits everything after it into a run of smaller keys (the left subtree) followed by the rest (the right subtree), which pins the shape exactly. Postorder works for the same reason, with the root at the end.

The inner while loop in fromPreorder is not quadratic

The stack holds the path of nodes still waiting for a right child, with keys decreasing from the bottom of the stack to the top; the root sits at the bottom only until its own right child arrives and pops it. Popping while the top key is smaller than v finds the node that v hangs off: the last one popped is the highest of them, and v becomes its right child. Every node is pushed once and popped at most once, so all the inner loops together do at most n pops and the whole build stays O(n).

Read more

Next up