#include<iostream>
#include<vector>

struct Tree {
	int data;
	Tree* left;
	Tree* rigth;

	Tree(const int& d, Tree* l = nullptr, Tree* r = nullptr) : data(d), left(l), rigth(r) {}
};

void freeTree(Tree* r) {
	if (r == nullptr)
		return;
	Tree* toDestroy = r;
	freeTree(r->left);
	freeTree(r->rigth);
	delete toDestroy;
}

int heigth(const Tree* root) {
	if (root == nullptr)
		return -1;
	return 1 + std::max(heigth(root->left), heigth(root->rigth));
}

int countNodesInSubtree(const Tree* root, int h) {
	if (root == nullptr) {
		return 0;
	}
	else if (h == 0) {
		return 1;
	}

	return 1 + countNodesInSubtree(root->left, h - 1) + countNodesInSubtree(root->rigth, h - 1);
}

bool isPerfectlyBalancedSubtree(const Tree* root, int h, int min = INT_MIN, int max = INT_MAX) {
	bool brokenBSTProperty = (root != nullptr && (root->data < min || root->data > max));

	if (root == nullptr || brokenBSTProperty)
		return false;
	else if (h == 0)
		return true;

	int lc = countNodesInSubtree(root->left, h - 1);
	int rc = countNodesInSubtree(root->rigth, h - 1);

	return std::abs(lc - rc) < 2 &&
		isPerfectlyBalancedSubtree(root->left, h - 1, min, root->data) &&
		isPerfectlyBalancedSubtree(root->rigth, h - 1, root->data, max);
}

int perfectlyBalancedCount(const Tree* root, int heigth, int globalHeigth) {
	if (globalHeigth < heigth || root == nullptr)
		return 0;

	return isPerfectlyBalancedSubtree(root, heigth) +
		perfectlyBalancedCount(root->left, heigth, globalHeigth - 1) +
		perfectlyBalancedCount(root->rigth, heigth, globalHeigth - 1);
}

int solution(const Tree* root, int h) {
	int globalHeigth = heigth(root);
	return perfectlyBalancedCount(root, h, globalHeigth);
}

Tree* makeTree(const std::vector<int> v) {
	if (v.empty())
		return nullptr;
	int mid = v.size() / 2;
	return new Tree(v[mid],
		makeTree(std::vector<int>(v.begin(), v.begin() + mid)),
		makeTree(std::vector<int>(v.begin() + mid + 1, v.end())));
}

void printBT(const std::string& prefix, const Tree* node, bool isLeft) {
	if (node != nullptr) {
		std::cout << prefix;

		std::cout << (isLeft ? "L---" : "R---");

		std::cout << node->data << std::endl;

		printBT(prefix + (isLeft ? "L   " : "    "), node->left, true);
		printBT(prefix + (isLeft ? "R   " : "    "), node->rigth, false);
	}
}

void printBT(const Tree* node) {
	printBT("", node, false);
}

int main() {
	Tree* t = makeTree({ 1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11, 12, 13, 14, 15});
	printBT(t);
	std::cout << solution(t, 4);
}