Двоичное дерево поиска находит преемника данного ключа (где ключ не должен находиться в дереве)

Question

Как бы я изменил следующий код, который я написал, чтобы учесть введенную пару k, которой нет в bst? Другими словами, как мне найти преемника ключа в бинарном дереве поиска, которого в нем нет?

public Record getSuccessor(Pair k, Node root) {

    if(root == null) {
        return null;
    }

    if(k.compareTo(root.getNodeRecord().getKey()) == 0) {
        if(root.getRightChild() != null) {
            return getSmallest(root.getRightChild());
        }
        else {
            return root.getParent().getNodeRecord();
        }
    }
    else {
        Record left = getSuccessor(k, root.getLeftChild());
        if(left != null) {
            return left;
        }
        return getSuccessor(k, root.getRightChild());
    }
}