Suma de rango

Lección 13 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

Debido a que el árbol mantiene cada valor ordenado, no es necesario inspeccionar cada nodo individual para sumar un rango: siempre que el valor de un nodo sea inferior a low, todo su subárbol izquierdo también estará por debajo de low y puede omitirse, y la misma lógica se aplica al subárbol derecho cuando el valor de un nodo es superior a high.

Un simple recorrido in-order que solo realice recursión en los subárboles que podrían contener valores dentro del rango es suficiente, aunque para este desafío un recorrido completo con un filtro también funciona.

Desafío

Fácil

Escribe una función rangeSum(tree, low, high) que devuelva la suma de cada valor en el árbol que se encuentre entre low y high, inclusive.

Pruébalo tú mismo

#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 p1 = atoi(strtok(NULL, " \n"));
    int result = rangeSum(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}