#include <iostream>
#include <queue>

using namespace std;

struct Node {
  char data;
  struct Node *left, *right;
  Node(char c, Node *l = nullptr, Node *r = nullptr)
    : data(c), left(l), right(r) {}
};

void printPreorder(struct Node* node) {
  if (node == nullptr) return;
  cout << node->data << " ";    // visit node
  printPreorder(node->left);    // visit left subtree
  printPreorder(node->right);   // visit right subtree
}

void preorderDemo() {
  Node* root =
    new Node('A',
      new Node('B', nullptr, new Node('C')),
      new Node('D',
        new Node('E', new Node('F'), new Node('G')),
        new Node('H', new Node('I'))
      )
    );
  cout << "Depth-first preorder traversal of binary tree\n";
  printPreorder(root);
}

void printPostorder(Node* node) {
  if (node == nullptr) return;
  printPostorder(node->left);    // visit left subtree
  printPostorder(node->right);   // visit right subtree
  cout << node->data << " ";     // visit node
}

void postorderDemo() {
  Node* root =
    new Node('A',
      new Node('B', nullptr, new Node('C')),
      new Node('D',
        new Node('E', new Node('F'), new Node('G')),
        new Node('H', new Node('I'))
      )
    );
  cout << "Depth-first postorder traversal of binary tree\n";
  printPostorder(root);
}

void printInorder(Node* node) {
  if (node == nullptr) return;
  printInorder(node->left);      // visit left subtree
  cout << node->data << " ";     // visit node
  printInorder(node->right);     // visit right subtree
}

void inorderDemo() {
  Node* root =
    new Node('A',
      new Node('B', nullptr, new Node('C')),
      new Node('D',
        new Node('E', new Node('F'), new Node('G')),
        new Node('H', new Node('I'))
      )
    );
  cout << "Depth-first inorder traversal of binary tree\n";
  printInorder(root);
}

void printBForder(Node* root) {
  if (root == nullptr) return;
  queue<Node *> q;                // Create an empty queue
  q.push(root);                   // Enqueue root
  while (!q.empty()) {
    Node *node = q.front();
    cout << node->data << " ";    // Print front of queue and remove it from queue
    q.pop();
    if (node->left != nullptr)
      q.push(node->left);         // Enqueue left child
    if (node->right != nullptr)
      q.push(node->right);        // Enqueue right child
  }
}

void bfDemo() {
  Node* root =
    new Node('A',
      new Node('B', nullptr, new Node('C')),
      new Node('D',
        new Node('E', new Node('F'), new Node('G')),
        new Node('H', new Node('I'))
      )
    );
  cout << "Breadth-first traversal of binary tree\n";
  printBForder(root);
}


int main() {
  preorderDemo(); cout << endl;
  postorderDemo(); cout << endl;
  inorderDemo(); cout << endl;
  bfDemo(); cout << endl;
}