// Arup Guha
// 11/12/2023
// Solution to COP 3502 Exam 2B Question 1

#include <stdio.h>
#include <stdlib.h>

typedef struct treenode {
    int data;
    struct treenode *left;
    struct treenode *right;
} treenode;

// Thursday exam solution.
// Returns the sum of the depths of the leaf nodes in the tree where root is at the
// depth, depth.
int sumleafdepths(treenode* root, int depth) {

	// Nothing to add.
    if (root == NULL) return 0;

	// This is a leaf node, its depth is depth, return it.
    if (root->left == NULL && root->right == NULL)
        return depth;

	// If we get here we weren't at a leaf node, recursively add both sides.
    return sumleafdepths(root->left, depth+1) + sumleafdepths(root->right, depth+1);
}

// Friday Exam Solution.
int numbetween(treenode* root, int low, int high) {

	// No values to count here.
    if (root == NULL) return 0;

	// Initialize our accumulator.
    int res = 0;

	// Update based on root as necessary.
    if (root->data >= low && root->data <= high) res++;

	// Go left, but only if we need to.
    if (low <= root->data) res += numbetween(root->left, low, high);

	// Go right, but only if we need to.
    if (high >= root->data) res += numbetween(root->right, low, high);

	// Ta da!
    return res;
}

treenode* mknode(int val) {
    treenode* tmp = malloc(sizeof(treenode));
    tmp->data = val;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}
treenode* insert(treenode* root, int value) {

    if (root == NULL) return mknode(value);

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

int main() {

    treenode* t = NULL;
    int vals[12] = {40,20,10,27,14,55,47,43,52,49,60,73};
    for (int i=0; i<12; i++)
        t = insert(t, vals[i]);
    printf("%d\n", sumleafdepths(t,0));
    printf("%d\n", numbetween(t, 22, 58));
    printf("%d\n", numbetween(t, 20, 58));
    printf("%d\n", numbetween(t, 20, 60));
    printf("%d\n", numbetween(t, 30, 35));
    return 0;
}