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

using namespace std;

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

  Node(int k, vector<Node*> cs = {}) : key(k), children(cs) {}
};

// Υψος
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 = new Node(7, {
    new Node(5, {
      new Node(3, {
        new Node(2)
      }),
      new Node(6),
      new Node(9)
    }),
    new Node(10, {
      new Node(11, {
        new Node(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";
}