#include "library.h"
#include <iostream>
using namespace std;

Tree::Tree()
{
    Head = nullptr;
}

Tree::~Tree()
{
    delete Head;
}

void Tree::Add(int value)
{
    if (Head == nullptr) {
        Element* CurElement = new Element(value);
        CurElement->value = value;
        Head = CurElement;
    }
    else {
        Element* PrevEl = nullptr;
        Element* Cur = Head;
        while (Cur != nullptr) {
            if (Cur->value <= value) {
                PrevEl = Cur;
                Cur = Cur->RightSon;
            }
            else {
                PrevEl = Cur;
                Cur = Cur->LeftSon;
            }
        }
        if (PrevEl != nullptr) {
            Element* CurElement = new Element(value);
            CurElement->value = value;
            if (PrevEl->value <= value) {
                PrevEl->RightSon = CurElement;
            }
            else PrevEl->LeftSon = CurElement;
        }
    }
}

int Tree::GetMaxElementCount()
{
    if (Head == nullptr) {
        return 0;
    }
    int MaxValue = -10000000;
    int count = 0;
    Element* current = Head;
    while (current != nullptr) {
        if (MaxValue < current->value) {
            count = 0;
            MaxValue = current->value;
        }
        ++count;
        current = current->RightSon;
    }
    return count;
}

int Tree::GetHeight(Element* node)
{
    if (node == nullptr) {
        return 0;
    }
    int Left = GetHeight(node->LeftSon);
    int Right = GetHeight(node->RightSon);
    return 1 + max(Left,Right);
}

bool Tree::isBalanced(Element* node)
{
    if (node == nullptr) return true;
    int leftHeight = GetHeight(node->LeftSon);
    int rightHeight = GetHeight(node->RightSon);
    if (abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(node->LeftSon) and isBalanced(node->RightSon);
}

bool Tree::isBalanced()
{
    return isBalanced(Head);
}

bool Tree::FindDivEL(Element* node, int& result)
{
    if (node == nullptr) {
        return false;
    }
    if (node->LeftSon != nullptr and node->value%node->LeftSon->value == 0) {
        result = node->value;
        return true;
    }
    if (node->RightSon != nullptr and node->value % node->RightSon->value == 0) {
        result = node->value;
        return true;
    }
    return FindDivEL(node->LeftSon, result) or FindDivEL(node->RightSon, result);
}

bool Tree::FindDivEL(int& result)
{
    return FindDivEL(Head,result);
}

Element::Element(int x)
{
    value = x;
}

Element::~Element()
{
    delete this->RightSon;
    delete this->LeftSon;
}