#include "solution_tree.h"
#include <deque>
#include <vector>
#include <utility>

using namespace std;

bool Solution(const Node* root) {
    deque <pair<const Node*, int>> d;
    vector<vector<int>> gens;

    if (root) {
        d.emplace_back(root, 0);
    }

    while (!d.empty()) {
        auto n = d.front().first;
        auto gen = d.front().second;

        d.pop_front();

        if (gen == gens.size()) {
            gens.push_back({ n->value });
        } else {
            gens.back().push_back({ n->value });
        }

        if (n->left) {
            d.emplace_back(n->left, gen + 1);
        }
        if (n->right) {
            d.emplace_back(n->right, gen + 1);
        }
    }

    int first = 0;
    for (int i = 0; i < gens.size(); ++i) {
        if (gens[i].size() == 2 ^ i) {
            first = i;
            continue;
        }
        break;
    }

    //first номер последнего сбалансированного уровня
    //gens.size() - 1 - это номер последнего поколения

    return (gens.size() - first - 1 <= 1);
}