FindInorderSuccessor.java

class BinaryTreeNode {
  BinaryTreeNode left;
  BinaryTreeNode right;
  int value;
}

public static BinaryTreeNode findInorderSuccessor(BinaryTreeNode root, int value) {
    if (root == null) {
        throw new IllegalArgumentException("Root cannot be null");
    }

    // Find the node for value in our tree
    // If we're given the node instead of a
    // value this whole block can be omitted.
    BinaryTreeNode find = null;
    BinaryTreeNode n = root;
    while (n != null) {
        if (n.value == value) {
            find = n;
            break;
        } else if (n.value > value) {
            n = n.left;
        } else {
            n = n.right;
        }
    }

    if (find == null) {
        throw new NoSuchElementException("No node with that value in this tree");
    }

    // If we have a right child, get the next element via
    // an in order traversal
    if (find.right != null) {
        BinaryTreeNode cur = find.right;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }

    BinaryTreeNode successor = null;
    n = root;
    while (n != find) {
        if (n.value > value) {
            successor = n;
            n = n.left;
        } else {
            n = n.right;
        }
    }

    return successor;
}