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.

60304050207080

This tree was a search tree until 20 and 60 were swapped. Is it a valid search tree? Each node must be inside a window: bigger than everything it is right of, smaller than everything it is left of. The root's window is open on both sides.

Check your understanding

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

  1. 50, with a window of open to open. Inside or outside?

    • Inside, fine
    • Outside, broken

    Answer: Inside, fine. 50 fits, so the window narrows for each child.

  2. 30, with a window of open to 50. Inside or outside?

    • Inside, fine
    • Outside, broken

    Answer: Inside, fine. 30 fits, so the window narrows for each child.

  3. 60, with a window of open to 30. Inside or outside?

    • Inside, fine
    • Outside, broken

    Answer: Outside, broken. The window came from ancestors, not just the parent. That is the check a parent-only comparison misses.

How it runs, step by step

  1. This tree was a search tree until 20 and 60 were swapped. Is it a valid search tree? Each node must be inside a window: bigger than everything it is right of, smaller than everything it is left of. The root's window is open on both sides.

    Validating a binary search tree using inherited bounds.

  2. 50 must be between open and open. It is. Its left child may be anything from open to 50, its right from 50 to open.

    50 must lie between open and open. It does.

  3. 30 must be between open and 50. It is. Its left child may be anything from open to 30, its right from 30 to 50.

    30 must lie between open and 50. It does.

  4. 60 must be between open and 30. It is not. 60 is on the wrong side of an ancestor, so this is not a search tree.

    60 must lie between open and 30. It does not.

  5. 60 broke its window, so this is not a search tree. Comparing it with only its parent would not have caught that.

    The tree is not a valid BST.

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