Binary search trees are normal binary trees in which data is organized in an ordered manner. Consider the same problem we encountered in the previous section, of the school keeping a student's records by using the passport numbers as a key. Figure 3.10 shows an example of how you can organize the data in a binary tree.

Note how at each node the left child has a key which is less than its own. On the other hand, the right child has a larger key. Shown in the diagram, the root node has a left child containing a key of a smaller value than the root key. On the other hand, the right child has a key of a larger value than the root.

This rule is repeated through the entire tree. In a binary search tree, the left child will always have a smaller key than the parent, while the right child will have a larger one. Using this binary search tree property, we can create efficient operations on the tree structure:

As a result of this simple rule, the tree exhibits important properties. For example, note how all the nodes that are descendants of the left child of the root node have a smaller key than the root. This property is valid for any node of the tree. All keys on the left subtree of a node will always have smaller keys, and vice versa.

Searching in a binary search tree requires us to follow some simple instructions. We start at the root and at each node, we ask ourselves: "Is the key we're looking for equal to less than, or greater than the key on this node?" If the key is equal, we're done and we have found our node. If the key is less, we follow the left child pointer, otherwise we follow the right one. We repeat this step until we find our key or hit a null child pointer.

Another important property of a binary search tree is being able to easily find the maximum and minimum key in the tree. Finding the maximum key in a binary tree is easy. Conceptually, this is the rightmost node. This can be found by starting at the root and always picking the right child until there isn't any right child to choose. The reverse is valid (picking the left child) for the minimum key.

The following code snippet shows the search implementation. In this implementation, we use the power of recursion to perform the search. We start by checking if the tree is empty by checking whether the root is null. If a root node is present, we compare the key and either return the value or recursively search the child nodes. To compare the key, we assume the provided key implements the comparable interface. Using Java's optional flat mapping makes our implementation much more concise:

public Optional<V> get(K key) {
  return Optional.ofNullable(root).flatMap(n -> get(key, n));
}
private Optional<V> get(K key, BinaryTreeNode<K, V> node) {
  if (((Comparable) key).compareTo(node.getKey()) == 0)
    return Optional.of(node.getValue());
  else if (((Comparable) key).compareTo(node.getKey()) < 0)
    return node.getLeft().flatMap(n -> get(key, n));
  else
    return node.getRight().flatMap(n -> get(key, n));
} 

Java's objectA.compareTo(objectB) method in the comparable interface returns a negative integer, zero, or a positive integer as objectA is less than, equal to, or greater than objectB. Thus, the following statement:

((Comparable) key).compareTo(node.getKey()) < 0 

Is conceptually the same as the following:

key < node.getKey()

Inserting in a binary tree follows the same logic as the search operation. We start from the root and keep on looking for a location where we need to create a new node. This is shown in the next code snippet. Like the search operation, this Java implementation is also recursive. If the root node is absent we just create a new one, otherwise we recursively insert the key value pair each time by choosing the left or right child depending on the value of the key.

We have three stopping conditions for the recursive call that are, as follows:

• When the key is equal to the one on the node, we simply overwrite the entry
• When the left child is not present, we create a new node with the key value pair
• When the right child is not present, we create a new node with the key value pair

The following code demonstrates the binary search tree insert operation:

if (((Comparable) key).compareTo(node.getKey()) == 0) {
  node.setKey(key);
  node.setValue(value);
} else if (((Comparable) key).compareTo(node.getKey()) <0) {
  if (node.getLeft().isPresent())
    put(key, value, node.getLeft().get());
  else
    node.setLeft(new BinaryTreeNode<>(key, value));
} else {
  if (node.getRight().isPresent())
    put(key, value, node.getRight().get());
  else
    node.setRight(new BinaryTreeNode<>(key, value));
}

Binary tree deletion requires matching the subtree structure with a number of patterns and performing different actions with each case. In some situations, it requires that you connect the subtree with the parent of the deleted node, which can be quite complex. For this reason, the deletion algorithm is beyond the scope of this book. For information on the deletion operation, you may refer to the following sources:

• The Art of Computer Programming, Volume 3: Sorting and Searching, by Donald Knuth.
• Paul E. Black, "binary search tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. January 26, 2015. Available at https://www.nist.gov/dads/HTML/binarySearchTree.html.