AlgoScope

Build and Validate a BST

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.

The player

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

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.

The code

Build and Validate a BST, in Python

def from_sorted(a, lo, hi):
    if lo > hi: return None
    mid = (lo + hi) // 2
    return Node(a[mid], from_sorted(a, lo, mid - 1), from_sorted(a, mid + 1, hi))

def is_bst(n, low, high):
    if n is None: return True
    if n.key <= low or n.key >= high: return False
    return is_bst(n.left, low, n.key) and is_bst(n.right, n.key, high)

def from_preorder(pre):                                         # the stack holds the right-open path
    root = Node(pre[0])
    stack = deque([root])
    for v in pre[1:]:
        last = None
        while stack and stack[-1].key < v: last = stack.pop()   # pop the smaller
        node = Node(v)
        if last is None: stack[-1].left = node                  # smaller than the top: its left child
        else: last.right = node                                 # right child of the last node popped
        stack.append(node)
    return root

Build and Validate a BST, in JavaScript

function fromSorted(a, lo, hi) {
  if (lo > hi) return null;
  const mid = Math.floor((lo + hi) / 2);
  return new Node(a[mid], fromSorted(a, lo, mid - 1), fromSorted(a, mid + 1, hi));
}

function isBst(n, low, high) {
  if (n === null) return true;
  if (n.key <= low || n.key >= high) return false;
  return isBst(n.left, low, n.key) && isBst(n.right, n.key, high);
}

function fromPreorder(pre) {                                // the stack holds the right-open path
  const root = new Node(pre[0]);
  const stack = [root];
  for (const v of pre.slice(1)) {
    let last = null;
    while (stack.length > 0 && stack[stack.length - 1].key < v) last = stack.pop();   // pop the smaller
    const node = new Node(v);
    if (last === null) stack[stack.length - 1].left = node;  // smaller than the top: its left child
    else last.right = node;                                  // right child of the last node popped
    stack.push(node);
  }
  return root;
}

Build and Validate a BST, in Kotlin

fun fromSorted(a: IntArray, lo: Int, hi: Int): Node? {
    if (lo > hi) return null
    val mid = (lo + hi) / 2
    return Node(a[mid], fromSorted(a, lo, mid - 1), fromSorted(a, mid + 1, hi))
}

fun isBst(n: Node?, low: Int, high: Int): Boolean {
    if (n == null) return true
    if (n.key <= low || n.key >= high) return false
    return isBst(n.left, low, n.key) && isBst(n.right, n.key, high)
}

fun fromPreorder(pre: IntArray): Node {                     // the stack holds the right-open path
    val root = Node(pre[0])
    val stack = ArrayDeque(listOf(root))
    for (v in pre.drop(1)) {
        var last: Node? = null
        while (stack.isNotEmpty() && stack.last().key < v) last = stack.removeLast()   // pop the smaller
        val node = Node(v)
        if (last == null) stack.last().left = node          // smaller than the top: its left child
        else last.right = node                               // right child of the last node popped
        stack.addLast(node)
    }
    return root
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

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.

Where this is used

Building a database index in bulkDatabases

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.

Deserializing a java.util.TreeMapStandard libraries

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.

Checking an index for corruptionOperations

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.

Nearest-neighbour search over pointsScientific computing

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

Backtracking

4 queens, with backtracking

Next lesson: Backtracking