#include <stdio.h>
#include "llrbContextWithVerifier.h"

unsigned int min_height(struct Node* node, unsigned int height) {
    if ((node->left == NULL) && (node->right == NULL)) return height;
    if (node->left  == NULL) return min_height(node->right, height+1);
    if (node->right == NULL) return min_height(node->left, height+1);

    unsigned int left_min  = min_height(node->left, height+1);
    unsigned int right_min = min_height(node->right, height+1);

    if (left_min < right_min) {
        return left_min;
    } else {
        return right_min;
    }
}

unsigned int max_height(struct Node* node, unsigned int height) {
    if ((node->left == NULL) && (node->right == NULL)) return height;
    if (node->left  == NULL) return max_height(node->right, height+1);
    if (node->right == NULL) return max_height(node->left, height+1);

    unsigned int left_max  = max_height(node->left, height+1);
    unsigned int right_max = max_height(node->right, height+1);

    if (left_max > right_max) {
        return left_max;
    } else {
        return right_max;
    }
}

void verify_tree_height(struct Node* root) {
    if (root == NULL) return;

    unsigned int min_h = min_height(root, 1);
    unsigned int max_h = max_height(root, 1);

    if (max_h >= 2*min_h) {
        printf("llrb-condition violated.\n");
        printf("\tmin-height %u", min_h);
        printf("\tmax-height %u", max_h);
        exit(EXIT_FAILURE);
    }
}