# Binary search trees

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.

## 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

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

## 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.

### 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

### 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

- 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

- 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):
- If the successor is a leaf node, remove its parent’s reference to the successor node
- If the successor has a right child, the parent’s reference to the successor node is replaced with the successor’s right child

## 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}
```