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

typedef struct bintreenode {
    int data;
    int height;
    struct bintreenode* left;
    struct bintreenode* right;
} btnode;

btnode* insert(btnode* root, int value);
int max(int a, int b);
void preorder(btnode* root);
void freetree(btnode* root);

int main() {

    btnode* root = NULL;
    root = insert(root, 20);

    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 9);
    root = insert(root, 7);
    root = insert(root, 25);
    root = insert(root, 35);
    root = insert(root, 27);
    root = insert(root, 40);
    root = insert(root, 33);
    root = insert(root, 2);
    preorder(root);
    freetree(root);
    return 0;
}

btnode* insert(btnode* root, int value) {

    // Base case - create a new node and return a pointer to it.
    if (root == NULL) {
        btnode* res = malloc(sizeof(btnode));
        res->data = value;
        res->height = 0;
        res->left = NULL;
        res->right = NULL;
        return res;
    }

    // Recursively insert to the left or right.
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);

    // Update the height based on potentially new heights on left and right.
    if (root->left != NULL)
        root->height = root->left->height + 1;
    if (root->right != NULL)
        root->height = max(root->height, root->right->height + 1);

    return root;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void preorder(btnode* root) {

    if (root != NULL) {
        printf("%d %d\n", root->data, root->height);
        preorder(root->left);
        preorder(root->right);
    }
}

void freetree(btnode* root) {
    if (root != NULL) {
        freetree(root->left);
        freetree(root->right);
        free(root);
    }
}