How to find the next biggest number in a binary search tree

Question

I have this function that I want to return the smallest node that is greater than or equal to the given node, or NULL if there is no such node.

I have written this pseudocode

// searches for the smallest node greater than or equal to a given node
static Node doTreeNext(Tree t, Node n, Node target) {
    // no record greater
    if (n == NULL) {
        return NULL;
    }

    if (n > target) {
        return doTreenNext(t, n->left, target);
    } else if (n <= target) {
        return doTreenNext(t, n->right, target);
    } 
}

The issue is if I had a tree like the following

https://i.sstatic.net/U8pEI.png

Where the expected output for when the target node is 12, is 13. The function currently will return NULL, since

13 > 12 (searches left) 11 < 12 (searches right, which is NULL)

My question is how do I stop it at 13?

Answer 1

Every time you hit a node that is larger your target value, you have a potential candidate for an answer, which should be taken unless the recursive answer call doesn't result in null.

What you should have something like the following pseudocode:

if (n > target) {
      candidate = search(n->left);
      if (candidate is null) {
           return n;
      } 
      else {
           return candidate;
      }
}
else {
     return search(n->right);
}