Binary search trees: search, insert, delete

Binary search in a sorted array takes $O(\log n)$, but insertion and deletion take $O(n)$ because they shift elements. In a linked list insertion is easy, but search is $O(n)$. A binary search tree (BST) tries to combine the good sides of both: as long as the tree stays short, search, insertion and deletion are $O(\log n)$.

The questions that almost certainly appear in the exam on this topic: insert in the given order and draw the tree, delete this node and draw the new tree, write the search path, is this tree a BST, what is the worst case. All of them rely on the few rules below.

The BST property

For every node x:

• every key in the left subtree of x is smaller than x,
• every key in the right subtree of x is larger than x.

In this course keys do not repeat. The most important consequence of this property: an inorder traversal gives the keys in increasing order.

We will use this tree throughout the page. The keys 50, 30, 70, 20, 40, 60, 80, 35, 45, 65 were inserted into an empty tree in this order:

            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80
         / \    \
       35  45    65

Inorder: 20 30 35 40 45 50 60 65 70 80. It is sorted, so it is a BST.

Search (find / contains)

Start at the root. If the key is smaller than the node, go left; if larger, go right; if equal, found. If you reach null, it is absent.

find 45: 50 30 40 45      found, 4 comp.
find 63: 50 70 60 65 null absent, 4 comp.

At each step you go down one level, so the cost is at most height + 1 comparisons: $O(h)$.

findMin always goes left (20), findMax always goes right (80). No comparison is even needed.

Insert

Descend as if searching for the new key. Where the search reaches null, create a new leaf. Insertion never moves existing nodes.

Inserting 63 into the tree above: 50 → 70 → 60 → 65 → the left of 65 is empty, so 63 goes there.

Insertion order determines the shape

The same set of keys gives very different trees with different orders:

order 1 2 3 4 5 6 7:       order 4 2 6 1 3 5 7:

1                                4
 \                             /   \
  2                           2     6
   \                         / \   / \
    3                       1   3 5   7
     \
      ...7   (height 6)             (height 2)

The tree on the left is really a linked list (degenerate tree). Search is $O(n)$. The one on the right is perfectly balanced, and search is $O(\log n)$. Inserting sorted data is very common in real life (timestamps, increasing IDs), so relying on a plain BST is risky.

PITFALL · “zigzag” inputs are bad too. 10, 90, 20, 80, 30, 70 is not sorted, but each element becomes the only child of the previous one. The result is again a chain, height 5. Sorted input is not required for a bad tree.

Delete (remove): three cases

First find the node to delete by searching. Then look at the number of children. Each of the three examples below starts from the original tree.

Case 1: leaf

Set the parent’s matching reference to null. Deleting 20: the left of 30 becomes null. Nothing else changes.

Case 2: one child

Skip the node: let the parent point directly to the grandchild. 60 has one child, 65. When 60 is deleted, the left of 70 becomes 65.

before:  70            after:  70
        /  \                  /  \
      60    80              65    80
        \
         65

The BST property is not broken: 65 was already in the left subtree of 70, and it stays there.

Case 3: two children

You cannot just remove the node, because you cannot attach two subtrees to a single parent reference. The solution: replace the node’s value with the value closest to it in sorted order. The rule used in this course is the inorder successor, that is, the smallest of the right subtree.

1. Go left all the way in the right subtree and find the smallest.
2. Copy that value into the node to be deleted.
3. Delete that value from the right subtree. The minimum of the right subtree cannot have a left child, so this second deletion is always case 1 or 2.

Let’s delete 30. 30 has two children (20 and 40). Its right subtree is (40, 35, 45), and the smallest is 35. 35 is copied up, and the leaf 35 is deleted:

            50
          /    \
        35      70
       /  \    /  \
     20   40  60   80
            \   \
            45   65

Program output: 50(35(20,40(-,45)),70(60(-,65),80)).

Now let’s delete the root (50) in the original tree. The smallest of the right subtree: 70 → 60, 60 has no left child, so the successor is 60. 60 is copied to the root. Since the old 60 has the single child 65, the second deletion is case 2: 65 becomes the left child of 70.

            60
          /    \
        30      70
       /  \    /  \
     20   40  65   80
         /  \
       35    45

TIP · the predecessor works too. Deletion also works with the largest of the left subtree (the inorder predecessor). If the exam does not say which rule to use, use the successor and note this in your answer.

Inorder successor

The smallest key larger than x. Two cases:

1. If x has a right subtree: the minimum of that subtree. In the main tree, successor(30) = 35.
2. If not: go up; the first ancestor that you reach x from its left side is the successor. successor(45): 45 is the right child of 40; 40 is the right child of 30; 30 is the left child of 50. The answer is 50.

If there is no parent reference, find it by searching from the root: while searching for x, record every node where you turned left as a “candidate”; the last candidate is the successor.

static Integer successor(Node root, int x) {
    Node t = root, succ = null;
    while (t != null) {
        if (x < t.element) { succ = t; t = t.left; }
        else t = t.right;
    }
    return succ == null ? null : succ.element;
}

The largest key (80) has no successor. The predecessor is symmetric: the maximum of the left subtree, or the first ancestor that you reach from its right side.

Height and complexity

The height of a tree with n nodes is between $\lfloor \log_2 n \rfloor$ and $n - 1$. If the keys are inserted in random order, the average depth is about $1.39 \log_2 n$, so the expected cost is $O(\log n)$. But “random” is not a guarantee. Those who want a guarantee move on to the balanced trees (AVL, red-black) of weeks 5 and 6.

Common mistakes

          45
        /    \
      22      67
     /  \    /  \
   10   30  55   80
        /     \
      27       60

          45
        /    \
      22      67
     /  \    /  \
   10   27  55   80
              \
               60

          55
        /    \
      22      67
     /  \    /  \
   10   30  60   80
        /
      27

        55
      /    \
    27      67
   /  \    /  \
 10   30  60   80

        50
       /  \
     30    70
    /  \   /
  20   55 60