// Binary Trees benchmark - recursive data structures
#include <stdio.h>
#include <stdlib.h>

typedef struct Tree {
    struct Tree* left;
    struct Tree* right;
} Tree;

Tree* make(int depth) {
    Tree* t = malloc(sizeof(Tree));
    if (depth == 0) {
        t->left = NULL;
        t->right = NULL;
    } else {
        t->left = make(depth - 1);
        t->right = make(depth - 1);
    }
    return t;
}

long check(Tree* t) {
    if (t->left == NULL) return 1;
    return 1 + check(t->left) + check(t->right);
}

void free_tree(Tree* t) {
    if (t->left) free_tree(t->left);
    if (t->right) free_tree(t->right);
    free(t);
}

int main() {
    int minDepth = 4;
    int maxDepth = 14;

    // Stretch tree
    int stretchDepth = maxDepth + 1;
    Tree* stretchTree = make(stretchDepth);
    printf("stretch tree check: %ld\n", check(stretchTree));
    free_tree(stretchTree);

    // Long lived tree
    Tree* longLivedTree = make(maxDepth);

    // Iterate through depths
    for (int depth = minDepth; depth <= maxDepth; depth += 2) {
        int iterations = 1 << (maxDepth - depth + 4);
        long sum = 0;
        for (int i = 0; i < iterations; i++) {
            Tree* t = make(depth);
            sum += check(t);
            free_tree(t);
        }
        printf("%d trees of depth %d check: %ld\n", iterations, depth, sum);
    }

    printf("long lived tree check: %ld\n", check(longLivedTree));
    free_tree(longLivedTree);
    return 0;
}