#include <iostream>
#include <string>

#include "tree.h"

using namespace std;

// Функция вычисляет расстояние от узла b до узла a снизу вверх.
// Если цикл достиг корня, то это означает, что либо узел b находится 
// в другой ветке, либо он находится ниже узла a в этой же ветке.
int length(tree *&a, tree *&b)
{
    tree *cur = b;
    int count = 0;
    while (cur != a)
    {
        if (cur->parent == NULL)
        {
            count = -1;
            break;
        }
        else
        {
            cur = cur->parent;
            count++;
        }
    }
    return count;
}

int solve(tree *&a, tree *&b)
{
    int ab = length(a, b);
    int ba = length(b, a);
    return max(ab, ba);
}

void create(tree *&t, int n, tree *parent)
{
    if (n > 0)
    {
        int x;
        cin >> x;
        t = node(x);
        t->parent = parent;
        
        int nl = n / 2;
        int nr = n - nl - 1;

        create(t->left, nl, t);
        create(t->right, nr, t);
    }
}

int main()
{
    int n;
    cout << "Введите количество узлов: ";
    cin >> n;
    tree *t = new tree;
    cout << "Введите содержимое узлов (желательно, уникальные):" << endl;
    create(t, n, NULL);

    print(t, log(n) / log(2));

    tree *node_a = NULL;
    {
        cout << "Введите содержимое узла a: ";
        int inf_a;
        cin >> inf_a;

        find(t, inf_a, node_a);

        if (node_a == NULL)
        {
            cout << "Узел a не найден в дереве" << endl;
            return 0;
        }
    }

    tree *node_b = NULL;
    {
        cout << "Введите содержимое узла b: ";
        int inf_b;
        cin >> inf_b;

        find(t, inf_b, node_b);

        if (node_b == NULL)
        {
            cout << "Узел b не найден в дереве" << endl;
            return 0;
        }
    }

    int x = solve(node_a, node_b);
    if (x < 0)
        cout << "Заданные узлы находятся в разных ветках" << endl;
    else if (x == 0)
        cout << "Заданные узлы равны" << endl;
    else
        cout << "Длина пути от узла a до узла b равна " << x << endl;
    return 0;
}