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

typedef struct Node
{
    char info;
    struct Node *left, *right;
} NODE;

NODE* insertElement(NODE*, int);
NODE* new_node(int );
void writeInorder(NODE* );
void writePreorder(NODE* );
void printAll(NODE* );
int heightoftree(NODE* );
void printGivenLevel(NODE* ,int );
int isBalanced(NODE* );
void delete_tree(NODE* );

int main()
{
    NODE *root = 0;
    FILE *dat;
    char c;

    if (dat = fopen("tekst.txt", "r"))
    {
        while((c = fgetc(dat))!=EOF)
        {
            c = toupper(c);
            if (c >= 'A' && c<='Z')
                root = insertElement(root, c);
        }
        fclose(dat);
        printf("Inorder: ");
        writeInorder(root);
        printf("\nPreorder: ");
        writePreorder(root);
        printf("\nLevel: ");
        printAll(root);
        if (isBalanced(root) == 1)
            printf("\nStablo je balansirano.");
        else printf("\nStablo nije balansirano.");
    }

    return 0;
}
NODE* new_node(int info)
{
    NODE* novi=(NODE*)malloc(sizeof(NODE));
    novi->left = novi->right = 0;
    novi->info = info;
    return novi;
}

NODE* insertElement(NODE* root, int info)
{
    if (root == 0)
        return new_node(info);
    if(info<root->info)
        root->left = insertElement(root->left, info);
    else if(info>root->info)
        root->right = insertElement(root->right, info);
    return root;
}

void writePreorder(NODE* root)
{
    if (root != 0)
    {
        printf("%c", root->info);
        writePreorder(root->left);
        writePreorder(root->right);
    }
}

void writeInorder(NODE* root)
{
    if (root != 0)
    {
        writeInorder(root->left);
        printf("%c", root->info);
        writeInorder(root->right);
    }
}

int visina(NODE*root)
{
    int max;
    if(root!=0)
    {
        int lijevi = visina(root->left);
        int desni = visina(root->right);
        if (lijevi > desni)
        {
            max = lijevi + 1;
            return max;
        }
        else
        {
            max = desni + 1;
            return max;
        }
    }
}

void printGivenLevel(NODE* root, int level)
{
    if(root == 0)
        return;
    if(level == 1)
        printf("%c", root->info);
    else if (level > 1)
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void printAll(NODE* root)
{
    int h = visina(root);
    int i;
    for (i=1; i<=h; i++)
        printGivenLevel(root, i);
}

int isBalanced(NODE* root)
{
    int lijevi, desni;

    if (root == NULL)
        return 1;
    lijevi = visina(root->left);
    desni = visina(root->right);

    if (fabs(desni-lijevi) <= 1 && isBalanced(root->left) && isBalanced(root->right))
        return 1;
    return 0;

}

void delete_tree(NODE *root)
{
  if (root != 0)
  {
    delete_tree(root->left);
    delete_tree(root->right);
    free(root);
  }
}