Binary Search Trees

A game server keeps its players sorted by score, so it can show each player the rival ranked just above them. A sorted array is great for that: binary search finds any score in about 20 steps among a million players. But players finish games all the time, and every new score has to be squeezed into the right place. In an array, that means shifting every item after it one slot to the right. Up to a million moves, for one insert.

You want the fast search of a sorted array without the expensive shifting. A binary search tree gives you both, as long as it keeps a sensible shape.

#The rule: smaller left, bigger right

A binary search tree (BST) is a binary tree with one rule, which holds at every node:

• every value in the node's left subtree is smaller than the node's value, and
• every value in its right subtree is bigger.

Look at the root. Everything smaller than it is somewhere on the left, everything bigger is on the right. So one comparison at the root throws away a whole side of the tree. That is binary search, built into the shape of the data instead of into array indexes.

You have already met one consequence. An inorder traversal visits the left subtree, then the node, then the right subtree. In a BST that means smaller values, then this one, then bigger values: the whole tree in sorted order.

#Search and insert follow one path

To find a value, start at the root and compare. Equal: found. Smaller: go left. Bigger: go right. If you step onto an empty child, the value is not in the tree.

Insert is the same walk. You search for the new value, and when you fall off the tree, the empty spot where you landed is exactly where it belongs. No other node moves.

insert(node, val):  if node is empty: return new node(val)  if val < node.val: node.left = insert(node.left, val)  if val > node.val: node.right = insert(node.right, val)  return node

// TreeNode is the same class as in Binary Trees.
function contains(node, val) {
  while (node !== null) {
    if (val === node.val) return true;
    node = val < node.val ? node.left : node.right; // throw away one side
  }
  return false;
}
 
// Returns the root of the tree with val added.
function insert(node, val) {
  if (node === null) return new TreeNode(val); // found the empty spot
  if (val < node.val) node.left = insert(node.left, val);
  else if (val > node.val) node.right = insert(node.right, val);
  return node; // a duplicate is ignored
}
 
let root = null;
for (const v of [40, 20, 60, 10, 30, 50, 70, 35]) root = insert(root, v);
contains(root, 35); // true
contains(root, 33); // false

# TreeNode is the same class as in Binary Trees.
def contains(node, val):
    while node is not None:
        if val == node.val:
            return True
        node = node.left if val < node.val else node.right  # throw away one side
    return False
 
# Returns the root of the tree with val added.
def insert(node, val):
    if node is None:
        return TreeNode(val)  # found the empty spot
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node  # a duplicate is ignored
 
root = None
for v in [40, 20, 60, 10, 30, 50, 70, 35]:
    root = insert(root, v)
contains(root, 35)  # True
contains(root, 33)  # False

insert returns the root of the updated subtree and the parent stores it back with node.left = …. That one habit handles the empty tree, where the new node becomes the root, with no special case.

Two more questions come free. The smallest value is the leftmost node: keep going left until you cannot. The largest is the rightmost.

#Delete: three cases

Removing a value is the only tricky operation, because the tree must stay valid. First find the node, then look at how many children it has.

1. No children: just remove it.
2. One child: the child moves up into its place. Everything under it was already on the correct side of the parent, so the rule still holds.
3. Two children: you cannot leave a hole with two subtrees hanging from it. Instead, find the next bigger value, called the successor. It is the leftmost node of the right subtree. Copy it into this node, then delete it from the right subtree. The successor has no left child (otherwise it would not be leftmost), so that second delete is case 1 or 2.

find the node with valif it has 0 or 1 child: replace it with that childelse:  next = leftmost node of its right subtree  copy next.val into the node  delete next.val from the right subtree

// Returns the root of the tree with val removed.
function remove(node, val) {
  if (node === null) return null; // val is not in the tree
  if (val < node.val) node.left = remove(node.left, val);
  else if (val > node.val) node.right = remove(node.right, val);
  else {
    if (node.left === null) return node.right; // 0 or 1 child:
    if (node.right === null) return node.left; // the child moves up
    let next = node.right;                     // 2 children: find the
    while (next.left !== null) next = next.left; // next bigger value
    node.val = next.val;                       // copy it here
    node.right = remove(node.right, next.val); // and remove the copy
  }
  return node;
}
 
root = remove(root, 20); // inorder: 10, 30, 35, 40, 50, 60, 70

# Returns the root of the tree with val removed.
def remove(node, val):
    if node is None:
        return None  # val is not in the tree
    if val < node.val:
        node.left = remove(node.left, val)
    elif val > node.val:
        node.right = remove(node.right, val)
    else:
        if node.left is None:   # 0 or 1 child:
            return node.right   # the child moves up
        if node.right is None:
            return node.left
        nxt = node.right        # 2 children: find the
        while nxt.left is not None:  # next bigger value
            nxt = nxt.left
        node.val = nxt.val      # copy it here
        node.right = remove(node.right, nxt.val)  # and remove the copy
    return node
 
root = remove(root, 20)  # inorder: 10, 30, 35, 40, 50, 60, 70

#Cost depends on the height

Search, insert and delete each walk one path from the root down, so each costs O(h), where h is the height. In a bushy tree, h is about log₂ n: 20 levels for a million values. That beats the sorted array, whose search is O(log n) but whose insert is O(n).

The catch: a BST's shape depends on the order you insert values. Insert 10, 20, 30, 40, 50 in that order and each new value is bigger than everything so far, so it always goes right. You get the stick from Binary Trees, with height n. Searching it is no faster than scanning a list.

Fixing that worst case is the job of balanced trees, which reshape themselves after each change so the height stays O(log n) whatever the insert order.

#Common mistakes

#Check yourself

#What to practise next

A BST answers "is this value here?" and "what comes next in order?". Often you only care about the smallest or the most urgent item. For that there is a simpler, faster structure: Heaps and Priority Queues.