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.

Build a balanced search tree from 1, 2, 3, 4, 5, 6, 7. Inserting in order would make a chain 7 deep. Instead, take the middle as the root, then do the same to each half.

Check your understanding

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

  1. Indices 0 to 6. Which value becomes this subtree's root?

    • 1
    • 4
    • 7

    Answer: 4. The middle index is 3. Taking the middle keeps both halves the same size.

  2. Indices 0 to 2. Which value becomes this subtree's root?

    • 1
    • 2
    • 3

    Answer: 2. The middle index is 1. Taking the middle keeps both halves the same size.

  3. Indices 0 to 0. Which value becomes this subtree's root?

    • 1
    • none

    Answer: 1. The middle index is 0. Taking the middle keeps both halves the same size.

  4. Indices 2 to 2. Which value becomes this subtree's root?

    • 3
    • none

    Answer: 3. The middle index is 2. Taking the middle keeps both halves the same size.

  5. Indices 4 to 6. Which value becomes this subtree's root?

    • 5
    • 6
    • 7

    Answer: 6. The middle index is 5. Taking the middle keeps both halves the same size.

  6. Indices 4 to 4. Which value becomes this subtree's root?

    • 5
    • none

    Answer: 5. The middle index is 4. Taking the middle keeps both halves the same size.

  7. Indices 6 to 6. Which value becomes this subtree's root?

    • 7
    • none

    Answer: 7. The middle index is 6. Taking the middle keeps both halves the same size.

How it runs, step by step

  1. Build a balanced search tree from 1, 2, 3, 4, 5, 6, 7. Inserting in order would make a chain 7 deep. Instead, take the middle as the root, then do the same to each half.

    Building a balanced BST from 7 sorted values by always taking the middle.

  2. Indices 0 to 6: the middle is index 3, 4. It is the root. Everything before it goes left, everything after goes right.

    4 becomes a node at depth 0.

  3. Indices 0 to 2: the middle is index 1, 2. It hangs left of 4. Everything before it goes left, everything after goes right.

    2 becomes a node at depth 1.

  4. Index 0 is a single value, so 1 is a leaf. It hangs left of 2.

    1 becomes a node at depth 2.

  5. Index 2 is a single value, so 3 is a leaf. It hangs right of 2.

    3 becomes a node at depth 2.

  6. Indices 4 to 6: the middle is index 5, 6. It hangs right of 4. Everything before it goes left, everything after goes right.

    6 becomes a node at depth 1.

  7. Index 4 is a single value, so 5 is a leaf. It hangs left of 6.

    5 becomes a node at depth 2.

  8. Index 6 is a single value, so 7 is a leaf. It hangs right of 6.

    7 becomes a node at depth 2.

  9. 7 values, height 3. Inserted in sorted order the same values would be 7 deep. Balanced from the start, every search is O(log n).

    The balanced tree has 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