I am trying to implement a function in C that will find the smallest int that is greater than or equal to a given int in an AVL. For example:

• if I have an AVL tree consisting of 1,2,3,4,5,6,7 and I put in 6, it should return 6.

• if I have an AVL tree consisting of 1,2,3,4,6,7 and I put in 5, it should return 6.

• if none are found, return -1.

I have found a case (there could be more) where this implementation fails. If I have an AVL tree of 1,2,3,4,5,6,7 and I input 3 it incorrectly returns 4. This case occurs when the ROOT is bigger than the input. I am not sure how to fix this though. There could also be other cases — if you could let me know that would be great.

Here is my attempt:

int findLeastGreatest(Node *root, int input) {
    // Never found
    if (root->left == NULL && root->right == NULL && root->data < input)
        return -1;
    // Found
    if ((root->data >= input && root->left == NULL) ||
        (root->data >= input && root->left->data < input)) 
        return root->data;

    if (root->data <= input)     
        return findLeastGreatest(root->right, input);
    else        
        return findLeastGreatest(root->left, input);
}

CodePudding user response：

Your function has problems: you are testing too many conditions together:

Here is a simpler approach:

• if the root is NULL, you should return -1;
• if the root->data < input, you should just recurse on the root->right node
• if root->data == input you should just return input.
• otherwise, you should recurse on the left node and return the result if found, otherwise return root->data.

Here is an implementation:

int findLeastGreatest(const Node *root, int input) {
    if (!root)
        return -1;
    if (root->data < input)
        return findLeastGreatest(root->right, input);
    if (root->data == input)
        return input;
    int value = findLeastGreatest(root->left, input);
    if (value == -1)
        return root->data;
    else
        return value;
}

If you are not required to produce a recursive version, here is a simpler version with a while loop:

int findLeastGreatest(const Node *root, int input) {
    int value = -1;
    while (root) {
        if (root->data < input) {
            root = root->right;
        } else {
            value = root->data;
            root = root->left;
        }
    }
    return value;
}

CodePudding user response：

I find it easier to write this function in a loop. The algorithm in the pseudocode below should work. The key idea is to not assign to bound unless the condition (node.key >= key) is true, in which case you must also traverse left to look for potentially smaller keys that satisfy the same condition. Otherwise, traverse right to look for larger keys that might satisfy.

least_greatest(node, key):
  bound = -1
  while node != NULL:
    if node.key >= key:
      bound = node.key  # found a bound, but it might not be the least bound
      node = node.left  # look for a smaller key
    else:
      node = node.right  # look for larger keys
  return bound

P.S. this function is called upper_bound in the C STL, and I've also seen this called "least upper bound".