#include "stdafx.h"
#include <iostream>

using namespace std;

struct elem { //структура на дървото
    int key;  //стойност на елемента
    elem* left; // ляво поддърво
    elem* right; //дясно поддърво
} *root = NULL; // инициализация на корена


void obhozdane(elem *t);
void add(int n, elem *&t);
void brojVarhoveLqvo(elem *t);
void brojVarhoveDqsno(elem *t);

int brojVarhove_lqvo = -1;
int brojVarhove_dqsno = -1;
bool balansirano = true;


void main()
{
    int broj;
    cout << "Broj elementi: ";
    cin >> broj;

    while (broj < 1) { //ако потребителя въведе число по-малко от 1 за брой, накарай го да въвежда пак число
        cout << "Nevaliden broj" << endl;
        cout << "Broj elementi: ";
        cin >> broj;
    }

    int number; //елемент на дървото
    cout << "Vavedete elementi: " << endl;

    for (int i = 0; i < broj; i++)
    {
        cin >> number;
        add(number, root);
    }

    obhozdane(root);

    if (balansirano)
        cout << "idealno balansirano" << endl;
    else
        cout << "ne e idealno balansirano" << endl;

    system("pause"); //да, има такова
}


//obhozdane prav red - корен, lqvo poddarvo dqsno poddarvo
void obhozdane(elem *t) //t -  цялото дърво или поддърво
{
    if (t)
    {
        obhozdane(t->left);
        obhozdane(t->right);

        bool hasLeaves = (t->left != NULL || t->right != NULL);

        if (hasLeaves) {
            brojVarhoveLqvo(t);
            brojVarhoveDqsno(t);

            if (abs(brojVarhove_lqvo - brojVarhove_dqsno) > 1) { //|5 - 3| = |3 - 5| = 2
                balansirano = false;
                return; //недей обхожда повече
            }

            brojVarhove_lqvo = -1;
            brojVarhove_dqsno = -1;
        }
    }
}

void add(int n, elem *&t)
{
    if (t == NULL) //в случай, че дървото няма елементи, или е след листо
    {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else
    {
        if (t->key < n) //ако е по-голямо от върха, сложи го от дясно
        {
            add(n, t->right);
        }
        else //ако е по-малко от върха, сложи го от дясно
        {
            add(n, t->left);
        }
    }
}

void brojVarhoveLqvo(elem *t) //t -  цялото дърво или поддърво
{
    if (t)
    {
        brojVarhoveLqvo(t->left);

        bool hasLeaves = (t->left != NULL || t->right != NULL);

        if (hasLeaves) {
            brojVarhove_lqvo++;
        }
    }
}

void brojVarhoveDqsno(elem *t) //t -  цялото дърво или поддърво
{
    if (t)
    {
        brojVarhoveDqsno(t->right);

        bool hasLeaves = (t->left != NULL || t->right != NULL);

        if (hasLeaves) {
            brojVarhove_dqsno++;
        }
    }
}