Successor Of A Value

Lesson 16 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

The in-order successor of a value is the smallest value in the tree that is strictly greater than it, the value that would come right after it in a sorted list. If the value is the maximum in the tree, it has no successor.

You can find it in one pass without ever sorting anything: walk down from the root, and every time you step right past a value that's too small, remember the last node you stepped left from as your best candidate so far.

Challenge

Easy

Write a function successor(tree, value) that returns the smallest value in the tree strictly greater than value, or -1 if none exists.

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int result = successor(tree, p0);
    printf("%d\n", result);
    return 0;
}