//
// Build a expression tree from an postfix representation
//

#include <iostream>
#include <string>

#include "queue.h"
#include "btree.h"
#include "bstree.h"

// Function used by traversals to print information
void Visit  (string& a, int d) { cout << a << " "; }

// Pretty printing function of a tree structure (again for traversals)
void Visitd (string& a, int d) 
{ 
  for (d *= 4; d > 0; d--) 
    cout << " "; 
  cout << a << endl; 
}

// 
// main function of the program
// 
int
main (int argn, char *argv[])
{
  int N;
  string input;
  BSTree<string> *bst = new BSTree<string>;

  // Read input from a file (if provided) or from stdin
  cin >> N;

  // Read N characeters and insert in BST
  for (int i = 0; i < N; i++)
    { 
      cin >> input;
      bst->Insert (input);
    }

  // Print the tree
  cout << bst->FindMin () << " " << bst->FindMax () << endl;
  bst->Preorder (Visitd); cout << endl;

  // Test delete one item
  cin >> input; bst->Delete (input);

  bst->Preorder (Visitd); cout << endl;

  // Print the expression 
    cout << "Preorder:   "; bst->Preorder (Visit); cout << endl;
    cout << "Inorder:    "; bst->Inorder   (Visit); cout << endl;
    cout << "Postorder:  "; bst->Postorder (Visit); cout << endl;

  delete bst;

  return 0;
}