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

struct tree_node
{
    int key;
    int value;
    struct tree_node *left_child, *right_child;
} *root;

void add_node(struct tree_node **root, int key, int value)
{
    if(*root=NULL)
    {
        if((*root)->key<=key)
            add_node(&(*root)->left_child,key,value);
        else
            add_node(&(*root)->right_child,key,value);
    }
else
{
    *root = (struct tree_node *)malloc(sizeof(struct tree_node));
        if(*root){
            (*root)->key = key;
            (*root)->value = value;
            (*root)->left_child = (*root)->right_child = NULL;
        }
}
}

void print_inorder(struct tree_node *root)
{
    if(root){
        print_inorder(root->left_child);
        printf("%d ",root->key);
        print_inorder(root->right_child);
    }
}

void print_preorder(struct tree_node *root)
{
    if(root){
        printf("%d ",root->key);
        print_preorder(root->left_child);
        print_preorder(root->right_child);
    }
}

void print_postorder(struct tree_node *root)
{
    if(root){
        print_postorder(root->left_child);
        print_postorder(root->right_child);
        printf("%d ",root->key);
    }
}

void remove_tree_nodes(struct tree_node **root)
{
    if(*root)
    {
        remove_tree_nodes(&(*root)->left_child);
        remove_tree_nodes(&(*root)->right_child);
        free(*root);
        *root = NULL;
    }
}

void ilosc_wew(struct tree_node *root, int *number)
{
    if(root)
    {
        if(root->left_child || root->right_child) (*number)++;
        ilosc_wew(root->left_child,number);
        ilosc_wew(root->right_child,number);
    }
}

void ilosc_zew(struct tree_node *root, int *number)
{
    if(root)
    {
        if(!(root->left_child) && !(root->right_child)) (*number)++;
        ilosc_zew(root->left_child,number);
        ilosc_zew(root->right_child,number);
    }
}

void czy_pelne(struct tree_node *root, int *number)
{
    if(root)
    {
        czy_pelne(root->left_child,number);
        (*number)++;
        czy_pelne(root->right_child,number);
    }
}

int height(struct tree_node *root)
{
    if(root == NULL) return 0;
    else
    {
       int lheight = height(root->left_child);
       int rheight = height(root->right_child);
       if(lheight>rheight)
        return lheight+1;
       else
        return rheight+1;
    }
}

int main()
{
    struct tree_node *root = NULL;

    add_node(&root, 8, 8);
    add_node(&root, 5, 5);
    add_node(&root, 1, 1);
    add_node(&root, 6, 6);
    add_node(&root, 10, 10);
    add_node(&root, 9, 9);
    add_node(&root, 12, 12);
    add_node(&root, 9, 9);

    printf("Inorder : "); print_inorder(root);

    puts(" ");

    int wysokosc = height(root);

    printf("\nWysokosc drzewa : %d \n", wysokosc);


    int licznik = 0;
    ilosc_wew(root, &licznik);

    printf("\n\nWewnetrznych wezlow : %d \n", licznik);

    licznik = 0;
    ilosc_zew(root, &licznik);

    printf("Zewnetrznych wezlow : %d \n", licznik);


    int potega = (int)pow(2.0,height(root));

    licznik = 0;
    czy_pelne(root, &licznik);

    if(licznik == potega-1) puts("\nDrzewo jest pelne");
    else puts("\nDrzewo nie jest pelne");

    remove_tree_nodes(&root);

    return 0;
}