PK

PKBytes

Explore tracks
Chapter 25: Binary Search Trees and Ordered Sets
25.02Intermediate / Advanced6 topics17 min4 interactive animations

BST updates

Changing a BST: insertion, the three cases of deletion (leaf, one child, two children), the transplant helper and the intuition behind Hibbard deletion.

Learning goals

  • Insert a key into the correct empty position
  • Delete a node in each of the three structural cases
  • Use transplant to replace one subtree by another
  • Explain why copying the successor keeps the ordering rule intact

Prerequisites

The BST invariant

Insertion is easy, because new keys always become leaves. Deletion is where the care goes: removing a node from the middle must keep every ordering relation intact.

25.02.1

Insert

To insert a key, search for it. If the search falls off the tree at an empty child, that is exactly where the key belongs: attach a new leaf. A new key always becomes a **leaf**, so no existing node moves and the ordering rule holds automatically. The cost is O(h).

In the “Insert” preset, inserting 35 into the 7-key tree compares it with 50, 30 and 40 and attaches it as the left child of 40; the inorder list [20, 30, 35, 40, 50, 60, 70, 80] stays sorted. The recursive version returns the (possibly new) subtree root so the parent can reattach it.

Java
1static Node insert(Node n, int key) {
2    if (n == null) return new Node(key);             // the empty spot: a new leaf
3    if (key < n.key) n.left = insert(n.left, key);
4    else if (key > n.key) n.right = insert(n.right, key);   // an equal key is ignored
5    return n;
6}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(h) recursion

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Your input

Try
Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13
Java
1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

0

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L3size=0An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2L6inserted=50 size=1Insert 50: the tree is empty, so it becomes the root.
3L7inserted=30 size=2Insert 30: compared with 50, it ends as the left child of 50.
4L8inserted=70 size=3Insert 70: compared with 50, it ends as the right child of 50.
5L7inserted=20 size=4Insert 20: compared with 50 → 30, it ends as the left child of 30.
6L8inserted=40 size=5Insert 40: compared with 50 → 30, it ends as the right child of 30.
7L7inserted=60 size=6Insert 60: compared with 50 → 70, it ends as the left child of 70.
8L8inserted=80 size=7Insert 80: compared with 50 → 70, it ends as the right child of 70.
9L12key=60 size=7Search for 60: start at the root.
10L14key=60 node=50 steps=160 > 50: go right; the whole left subtree is ruled out.
11L14key=60 node=70 steps=260 < 70: go left; the whole right subtree is ruled out.
12L14key=60 node=60 steps=360 == 60: found after 3 comparisons.
13L14return=true steps=3contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.
25.02.2

Delete leaf

Deleting a **leaf** is the easy case: cut the link from its parent. Nothing else in the tree depends on it. In the “Delete a leaf” preset, removing 20 leaves the inorder sequence [30, 40, 50, 60, 70, 80], which is still sorted.

Java
1static void removeLeaf(Node parent, Node leaf) {     // a leaf: just cut the link
2    if (parent.left == leaf) parent.left = null;
3    else parent.right = null;
4}

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Your input

Try
Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13
Java
1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

0

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L3size=0An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2L6inserted=50 size=1Insert 50: the tree is empty, so it becomes the root.
3L7inserted=30 size=2Insert 30: compared with 50, it ends as the left child of 50.
4L8inserted=70 size=3Insert 70: compared with 50, it ends as the right child of 50.
5L7inserted=20 size=4Insert 20: compared with 50 → 30, it ends as the left child of 30.
6L8inserted=40 size=5Insert 40: compared with 50 → 30, it ends as the right child of 30.
7L7inserted=60 size=6Insert 60: compared with 50 → 70, it ends as the left child of 70.
8L8inserted=80 size=7Insert 80: compared with 50 → 70, it ends as the right child of 70.
9L12key=60 size=7Search for 60: start at the root.
10L14key=60 node=50 steps=160 > 50: go right; the whole left subtree is ruled out.
11L14key=60 node=70 steps=260 < 70: go left; the whole right subtree is ruled out.
12L14key=60 node=60 steps=360 == 60: found after 3 comparisons.
13L14return=true steps=3contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.
25.02.3

Delete one-child

A node with **one child** is bypassed: its parent adopts the child, in the place where the node used to hang. The child's whole subtree moves up one level and the ordering still holds, because the subtree sat on the correct side of the removed node's ancestors already.

The “Delete, one child” preset removes 60, which has only the right child 65: the node 70 now has 65 as its left child, and the inorder sequence is [20, 30, 50, 65, 70, 80].

Java
1static void bypass(Node parent, Node node) {         // node has exactly one child: the parent adopts it
2    Node child = node.left != null ? node.left : node.right;
3    if (parent.left == node) parent.left = child;
4    else parent.right = child;
5}

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Your input

Try
Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13
Java
1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

0

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L3size=0An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2L6inserted=50 size=1Insert 50: the tree is empty, so it becomes the root.
3L7inserted=30 size=2Insert 30: compared with 50, it ends as the left child of 50.
4L8inserted=70 size=3Insert 70: compared with 50, it ends as the right child of 50.
5L7inserted=20 size=4Insert 20: compared with 50 → 30, it ends as the left child of 30.
6L8inserted=40 size=5Insert 40: compared with 50 → 30, it ends as the right child of 30.
7L7inserted=60 size=6Insert 60: compared with 50 → 70, it ends as the left child of 70.
8L8inserted=80 size=7Insert 80: compared with 50 → 70, it ends as the right child of 70.
9L12key=60 size=7Search for 60: start at the root.
10L14key=60 node=50 steps=160 > 50: go right; the whole left subtree is ruled out.
11L14key=60 node=70 steps=260 < 70: go left; the whole right subtree is ruled out.
12L14key=60 node=60 steps=360 == 60: found after 3 comparisons.
13L14return=true steps=3contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.
25.02.4

Delete two-child

A node with **two children** cannot simply be cut out. Instead, replace its key by the key of its **inorder successor** (the minimum of its right subtree), then delete that successor node from the right subtree. The successor has no left child by definition, so removing it falls into the easy one-child or leaf case. The new key is larger than everything on the left and smaller than everything on the right, so the ordering holds.

In the “Delete, two children” preset, removing 30 copies the successor 40 into its place and then removes the old node 40; the inorder sequence becomes [20, 40, 50, 60, 70, 80]. Using the predecessor (the maximum of the left subtree) works just as well.

Java
1static Node delete(Node n, int key) {
2    if (n == null) return null;                      // the key is not in the tree
3    if (key < n.key) n.left = delete(n.left, key);
4    else if (key > n.key) n.right = delete(n.right, key);
5    else {
6        if (n.left == null) return n.right;          // zero or one child: splice the node out
7        if (n.right == null) return n.left;
8        Node s = n.right;
9        while (s.left != null) s = s.left;           // two children: the inorder successor
10        n.key = s.key;                               // copy its key up
11        n.right = delete(n.right, s.key);            // then remove the successor node
12    }
13    return n;
14}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(h) recursion

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Your input

Try
Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13
Java
1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

0

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L3size=0An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2L6inserted=50 size=1Insert 50: the tree is empty, so it becomes the root.
3L7inserted=30 size=2Insert 30: compared with 50, it ends as the left child of 50.
4L8inserted=70 size=3Insert 70: compared with 50, it ends as the right child of 50.
5L7inserted=20 size=4Insert 20: compared with 50 → 30, it ends as the left child of 30.
6L8inserted=40 size=5Insert 40: compared with 50 → 30, it ends as the right child of 30.
7L7inserted=60 size=6Insert 60: compared with 50 → 70, it ends as the left child of 70.
8L8inserted=80 size=7Insert 80: compared with 50 → 70, it ends as the right child of 70.
9L12key=60 size=7Search for 60: start at the root.
10L14key=60 node=50 steps=160 > 50: go right; the whole left subtree is ruled out.
11L14key=60 node=70 steps=260 < 70: go left; the whole right subtree is ruled out.
12L14key=60 node=60 steps=360 == 60: found after 3 comparisons.
13L14return=true steps=3contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.
25.02.5

Transplant

**Transplant** is the helper that makes the cases uniform: replace the subtree rooted at u by the subtree rooted at v (which may be null) in u's parent. It only fixes the parent's link, and the child's parent pointer. Deletion then reads as: no left child, transplant the right child; no right child, transplant the left; otherwise find the successor y, move it up (first transplanting its own right child into its old place if it is not z's direct child) and give it z's left subtree.

This version moves the successor **node** instead of copying keys, which matters when other code keeps references to nodes (iterators, caches): the node being deleted is the one that disappears. It needs parent pointers in the nodes.

Java
1static class Node {
2    int key;
3    Node left, right, parent;
4    Node(int key) { this.key = key; }
5}
6static Node root;
7
8static void transplant(Node u, Node v) {             // replace the subtree rooted at u by the one rooted at v
9    if (u.parent == null) root = v;
10    else if (u == u.parent.left) u.parent.left = v;
11    else u.parent.right = v;
12    if (v != null) v.parent = u.parent;
13}
14
15static void delete(Node z) {
16    if (z.left == null) transplant(z, z.right);
17    else if (z.right == null) transplant(z, z.left);
18    else {
19        Node y = z.right;
20        while (y.left != null) y = y.left;           // the successor
21        if (y.parent != z) {
22            transplant(y, y.right);                  // y leaves its old place
23            y.right = z.right;
24            y.right.parent = y;
25        }
26        transplant(z, y);                            // y takes z's place
27        y.left = z.left;
28        y.left.parent = y;
29    }
30}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(1)

25.02.6

Hibbard deletion intuition

The method above is **Hibbard deletion** (1962): a two-child node is replaced by its successor. Why does it keep the invariant? Every key to the left of the node is smaller than the successor (the successor is bigger than the node, which is bigger than the left subtree) and every key to its right, other than the successor itself, is bigger (the successor is the *smallest* of that right subtree). The replaced position is therefore a valid root for both subtrees.

The method is correct but asymmetric: it always draws from the right side. It is known from the literature that after a long sequence of random insertions and deletions done this way, trees tend to become taller than the logarithmic height a random tree has. Alternating between successor and predecessor, or using balanced trees (the next chapter), avoids the drift.

Practice ladder

Now try it yourself

Easy

  • Insert into a Binary Search Tree
  • Trim a Binary Search Tree

Medium

  • Delete Node in a BST
  • Convert BST to Greater Tree

Advanced

  • Delete Nodes And Return Forest
  • Balance a Binary Search Tree

Key takeaways

  • A new key always becomes a leaf, found by searching until the tree runs out.
  • Deleting a leaf cuts a link; a node with one child is bypassed by its parent.
  • A node with two children takes the key of its inorder successor, which is then deleted from the right subtree.
  • Transplant replaces one subtree by another and unifies the deletion cases.
  • Always drawing from one side can distort the tree over time; balanced trees avoid it.