#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Node {  // Κόμβος με πληροφορία τύπου int
  int key;
  vector<Node *> children;
};

// Δημιουργία κόμβου
Node *newNode(int newKey) {
  Node *temp = new Node;
  temp->key = newKey;
  return temp;
}

// Υψος
int height(Node *r) {
  if (r == nullptr) return -1;
  int h = -1;
  for (Node *child: r->children)
    h = max(h, height(child));
  return h+1;
}

// Αναζήτηση
Node * searchTree(Node *r, int k) {
  if (r == nullptr) return nullptr;
  if (r->key == k) return r;
  for (Node *child: r->children) {
    Node *s = searchTree(child, k);
    if (s != nullptr) return s;
  }
  return nullptr;
}

void LevelOrderTraversal(Node * root) {	 // Διάσχιση κατά πλάτος
  if (root == nullptr) return;
  queue<Node *> q;
  q.push(root);
  while (!q.empty()) {
    int n = q.size();		// τρέχον μέγεθος της ουράς q
    while (n > 0) {
      Node * p = q.front();	 // αφαίρεση του πρώτου στοιχείου της ουράς
      q.pop(); n--;
      cout << p->key << " ";	// εκτύπωση
      // Αν έχει παιδιά, βάλε τα στην ουρά
      for (Node *child : p->children)
        q.push(child);
    }
    cout << endl;		// επόμενο επίπεδο
  }
}

int main() {
  Node *root = newNode(7);                  // tragic!
  root->children.push_back(newNode(5));
  root->children.push_back(newNode(10));
  root->children[0]->children.push_back(newNode(3));		// root->children[0] περιέχει το 5
  root->children[0]->children.push_back(newNode(6));
  root->children[0]->children.push_back(newNode(9));
  root->children[0]->children[0]->children.push_back(newNode(2));
  root->children[1]->children.push_back(newNode(11));		// root->children[0] περιέχει 10
  root->children[1]->children[0]->children.push_back(newNode(4));

  cout << "Level order traversal\n";
  LevelOrderTraversal(root);
  cout << "h=" << height(root) << endl;

  Node *S = searchTree(root, 99);
  if (S != nullptr)
      cout << "found\n";
  else
      cout << "not found\n";
}