Binary search trees

Jan 12, 2023 (Updated Jan 16, 2023)

A binary search tree is a binary tree sorted such that for each node, every node’s key in its left subtree is less than or equal to its key’s value, and every node’s key in its right subtree is greater than or equal to its key’s value.

Operation	Average	Worst
Access	$\htmlClass{text-green}{\Theta(\log(n))}$	$\htmlClass{text-yellow}{\mathcal{O}(n)}$
Insert	$\htmlClass{text-green}{\Theta(\log(n))}$	$\htmlClass{text-yellow}{\mathcal{O}(n)}$
Delete	$\htmlClass{text-green}{\Theta(\log(n))}$	$\htmlClass{text-yellow}{\mathcal{O}(n)}$

The sorting properties of a binary search tree allow for efficient searching, since for each comparison up to half of the remaining subtree can be eliminated.

(original)

Maximum and minimum

To find the maximum key in a binary search tree (or subtree), starting with the root node:

Get the right child of the current node
- If no right child exists, the current node is the maximum
- Otherwise, repeat with the right child

(original)

To find the minimum key in a binary search tree (or subtree), starting with the root node:

Get the left child of the current node
- If no left child exists, the current node is the minimum
- Otherwise, repeat with the left child

(original)

Successor and predecessor

A node’s successor is the node with the smallest key greater than that node’s key. To find a node’s successor:

If the node has a right subtree, the successor is the minimum key in that subtree
Otherwise, traverse the node’s ancestors until:
- A node is found which is the left child of its parent – this node’s parent is the successor
- If no such node exists, there is no successor

A node’s predecessor is the node with the largest key less than that node’s key. To find a node’s predecessor:

If the node has a left subtree, the predecessor is the maximum key in that subtree
Otherwise traverse the nodes’ ancestors until:
- A node is found which is the right child of its parent – this node’s parent is the predecessor
- If no such node exists, there is no predecessor

In-order traversal

For each node:

Recursively traverse the left subtree
“Visit” the node
Recursively traverse the right subtree

The implementation below has an example of this recursive function.

Operations

Access

Beginning with the root node, compare the node’s key value to the search key:

If the keys are equal, the search is successful.
Otherwise, repeat the comparison with the left child (if the search key is less than the current node’s) or the right child (if it is greater than the current node’s).
- If the correct child does not exist, the key does not exist in the tree.

(original)

Insertion

Beginning with the root node, compare the node’s key value to the insertion key:

If the insertion key is less than the current node:
- If the left child does not exist, insert as the left child
- Otherwise, repeat the comparison with the left child
Likewise, if the insertion key is greater than the current node:
- If the right child does not exist, insert as the right child
- Otherwise, repeat the comparison with the right child

(original)

Deletion

First, access the node to be deleted. If it is found, there are 3 scenarios:

Leaf node (no left or right child):
- If the node has a parent, remove its reference to the node
- If the node is the root, the tree is now empty

(original)

Internal node (1 child):
- If the node has a parent, its reference to the node is replaced with the child node
- If the node is the root, the child becomes the new root

(original)

Internal node (2 children):
- Find the node’s successor (since the node always has a right subtree in this scenario, the successor will always be contained in that subtree)
- Replace the node’s key/value with that of the the successor
- Delete the successor from the right subtree, which reduces to repeating scenario 1 or 2 above for the successor (since the successor is the left-most node in the subtree, it will always have either 0 children or 1 right child):
  1. If the successor is a leaf node, remove its parent’s reference to the successor node
  2. If the successor has a right child, the parent’s reference to the successor node is replaced with the successor’s right child

(original)

Implementation

This generic example implementation stores key-value pairs and is adaptable as a map ADT :

  1public class BinarySearchTree<K extends Comparable<K>,V> {
  2    private class Node {
  3        private K key;
  4        private V value;
  5        private Node left, right;
  6
  7        public Node(K key, V value) {
  8            this.key = key;
  9            this.value = value;
 10        }
 11    }
 12
 13    private int size = 0;
 14    private Node root = null;
 15
 16    public int size() { return size; }
 17
 18    public boolean isEmpty() { return size == 0; }
 19
 20    public V search(K key) {
 21        Node result = findNode(key);
 22        return result != null ? result.value : null;
 23    }
 24
 25    private Node findNode(K key) {
 26        Node current = root;
 27        while (current != null && !key.equals(current.key)) {
 28            if (lt(key, current.key))
 29                current = current.left;
 30            else
 31                current = current.right;
 32        }
 33        return current;
 34    }
 35
 36    public V insert(K key, V value) {
 37        Node parent = null;
 38        Node current = root;
 39
 40        while (current != null) {
 41            if (key.equals(current.key)) {
 42                // replace the existing key
 43                V result = current.value;
 44                current.value = value;
 45                return result;
 46            }
 47
 48            parent = current;
 49            if (lt(key, current.key))
 50                current = current.left;
 51            else
 52                current = current.right;
 53        }
 54
 55        Node newNode = new Node(key, value);
 56        if (parent == null)
 57            root = newNode;
 58        else if (lt(key, parent.key))
 59            parent.left = newNode;
 60        else
 61            parent.right = newNode;
 62
 63        size++;
 64        return null;
 65    }
 66
 67    public V remove(K key) {
 68        // find the node to remove, and its parent
 69        Node parent = null;
 70        Node current = root;
 71        while (current != null && !key.equals(current.key)) {
 72            parent = current;
 73            if (lt(key, current.key))
 74                current = current.left;
 75            else
 76                current = current.right;
 77        }
 78
 79        if (current == null) return null; // key not found
 80
 81        V result = current.value;
 82
 83        // leaf node case
 84        if (current.left == null && current.right == null) {
 85            skipNode(parent, current, null);
 86        }
 87        // one child case
 88        else if (current.right == null || current.left == null) {
 89            Node child = current.right == null ? current.left : current.right;
 90            skipNode(parent, current, child);
 91        }
 92        // two children case
 93        else {
 94            // find the node's in-order successor, and its parent
 95            parent = current;
 96            Node successor = current.right;
 97
 98            while (successor != null) {
 99                parent = successor;
100                successor = successor.left;
101            }
102
103            // replace the current node with its successor
104            current.key = successor.key;
105            current.value = successor.value;
106
107            // remove the now-duplicated successor
108            skipNode(parent, successor, successor.right);
109        }
110        size--;
111        return result;
112    }
113
114    private void skipNode(Node parent, Node deprecated, Node child) {
115        if (parent == null)
116            root = child;
117        else if (parent.left == deprecated)
118            parent.left = child;
119        else
120            parent.right = child;
121    }
122
123    public void forEach(BiConsumer<K, V> consumer) {
124        inOrderWalk(root, (n) -> consumer.accept(n.key, n.value));
125    }
126
127    private void inOrderWalk(Node root, Consumer<Node> consumer) {
128        if (root != null) {
129            inOrderWalk(root.left, consumer);
130            consumer.accept(root);
131            inOrderWalk(root.right, consumer);
132        }
133    }
134
135    private boolean lt(K key, K key2) { return key.compareTo(key2) < 0; }
136}