#include <iostream>
#include <cstring>
#include <vector> // Б подточка

template <typename T>
struct Node {
	T data;
	Node<T> *left, *right;
	Node(const T& data, Node<T>* left = nullptr, Node<T>* right = nullptr) : data(data), left(left), right(right) {}
};

void freeTree(const Node<char>* tree) {
	if (tree == nullptr) return;
	freeTree(tree->left);
	freeTree(tree->right);
	delete tree;
}

/* Подточка А */

bool checkWord(const Node<char>* tree, const char* start, const char* end) {
	if (start == end)
		return true;
	if (start == nullptr || tree == nullptr)
		return false;
	if (*start != tree->data)
		return false;

	return checkWord(tree->left, start + 1, end) || checkWord(tree->right, start + 1, end);
}

bool readWord(const Node<char>* tree, const char* word) {
	if (strlen(word) < 4)
		throw std::runtime_error("Word length cannot be less than 4!");

	const char* endWord = word;
	while (*endWord != '\0') endWord++;

	const char* separator = word + 1;
	while (separator != endWord) {
		if (checkWord(tree->right, word, separator) && checkWord(tree->left, separator, endWord))
			return true;
		separator++;
	}
	return false;
}

void A() {
	const Node<char>* t =
		new Node<char>('F',
				new Node<char>('B',
					new Node<char>('A'),
					new Node<char>('D',
						new Node<char>('C'),
						new Node<char>('E'))),
				new Node<char>('G',
					nullptr,
					new Node<char>('I',
						new Node<char>('H'),
						nullptr)));

	std::cout << readWord(t, "GIBDC") << readWord(t, "GIBD") << readWord(t, "GIBCD") << readWord(t, "GHBD") << std::endl;
	freeTree(t);
}

/* Подточка Б */

bool risingOrder(std::vector<char>& v) {
	for (size_t i = 0; i < v.size() - 1; i++) {
		if (v[i] > v[i+1]) return false;
	}
	return true;
}

void getLevel(const Node<char>* tree, size_t level, std::vector<char>& out) {
	if (level == 0) return;
	if (tree->left != nullptr) getLevel(tree->left, level - 1, out);
	if (level == 1) {
		out.push_back(tree->data);
		return;
	}
	if (tree->right != nullptr) getLevel(tree->right, level - 1, out);
}

size_t minLevel(const Node<char>* tree) {
	std::vector<char> temp;
	size_t i = 1;
	getLevel(tree, i, temp);
	while (!temp.empty()) {
		i++;
		temp.clear();
		getLevel(tree, i, temp);
		if (risingOrder(temp)) break;
	}
	return (temp.empty()) ? 0 : i;
}

void B() {
	const Node<char>* t =
		new Node<char>('F',
				new Node<char>('Z',
					new Node<char>('Z'),
					new Node<char>('D',
						new Node<char>('C'),
						new Node<char>('E'))),
				new Node<char>('G',
					nullptr,
					new Node<char>('I',
						new Node<char>('H'),
						nullptr)));

	std::cout << minLevel(t) << std::endl;
	freeTree(t);
}

int main() {
	//A();
	B();
}