Minimum, Maximum, and Successor

The smallest value in a binary search tree is the leftmost value. Start at the root and keep going left until there is no left child. In our tree that path goes 50, 30, 20, and each step skips a right subtree:

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │░70░│
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│█20█│    │░40░│      │░60░│    │░80░│
╰────╯    ╰────╯      ╰────╯    ╰────╯

20 has no left child, so 20 is the minimum. Any smaller value would have to be to the left, and once there is no left child, there is nowhere smaller to go. The maximum is found the same way, following right children. In this tree, that gives 80.

Here is the code for the minimum node:

// Assumes node is not null.
private Node<T> minNode(Node<T> node) {
  while (node.left != null) {
    node = node.left;
  }
  return node;
}

It assumes the subtree it is given is not empty. On an empty subtree there is no minimum. maxNode is the same loop with right in place of left.

Successor and predecessor

The in-order successor of a value is the next value after it in sorted order. If a node has a right subtree, its successor is the minimum value in that right subtree. For 50, the right subtree is rooted at 70. Going left from 70 reaches 60, which has no left child, so 60 is the successor of 50:

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │█60█│    │░80░│
╰────╯    ╰────╯      ╰────╯    ╰────╯

For 30, the right subtree is just 40, so 40 is the successor of 30.

The in-order predecessor is the same idea with left and right swapped: the previous value in sorted order. If a node has a left subtree, its predecessor is the maximum value in that left subtree. For 50, that is 40.

A node without a right subtree may still have a successor. In that case the successor is one of its ancestors. The same holds for a node without a left subtree: its predecessor is one of its ancestors. For example, 60 has no left child, so its predecessor is 50. 40 has no right child, so its successor is 50.