Lesson 17.3 · Binary Search Trees

In-Order Tricks and Deleting

In-order visits a BST in sorted order, which answers k-th smallest, closest values and successor questions. Deleting a node with two children borrows its in-order successor.

14 min

Think of it like this

Reading the spines of books on a sorted shelf from left to right: the third book you read is the third smallest. Removing a book from the middle means sliding its right-hand neighbour into the gap.

1.Sorted for free

Any question about rank ("k-th smallest"), neighbours ("next larger"), or pairs (two values adding to k) on a BST can reuse the in-order walk. Stop early when you've seen k values; the cost is O(h + k), not O(n).

2.Deleting a node

Three cases. Leaf: just remove it. One child: replace the node with that child. Two children: copy in the in-order successor (the smallest value in the right subtree, found by going right once and then left as far as possible) and delete that successor from the right subtree, where it has at most one child.

▶ Dry run: Deleting 3 from [5, 3, 6, 2, 4, null, 7]root = [5, 3, 6, 2, 4, null, 7], key = 3

Step 1/33 has two children, so it can't simply be removed.

3.TreeMap: the balanced BST in Java

You rarely write a balanced BST by hand. TreeMap gives O(log n) put, get and remove plus ordered queries: floorKey (largest ≤ x), ceilingKey (smallest ≥ x), firstKey, lastKey, headMap and tailMap. Use it when you need a sorted map that changes over time, for example in calendar booking or sliding-window medians.

Main.java

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> m = new TreeMap<>();
        m.put(10, "ten"); m.put(20, "twenty"); m.put(30, "thirty");
        System.out.println(m.floorKey(25));        // largest key <= 25
        System.out.println(m.ceilingKey(25));      // smallest key >= 25
        System.out.println(m.floorKey(5));         // none
        System.out.println(m.headMap(20));         // keys < 20
        System.out.println(m.tailMap(20, true));   // keys >= 20
    }
}

Output

20
30
null
{10=ten}
{20=twenty, 30=thirty}

Remember

In-order = sorted.
Successor = leftmost node of the right subtree.
TreeMap's floor/ceiling are O(log n).

Common mistakes

Forgetting floorKey returns null (unboxing it into int throws NullPointerException).

Command Palette

In-Order Tricks and Deleting

1.Sorted for free

2.Deleting a node

3.TreeMap: the balanced BST in Java