#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <stdexcept>
#include "binTreeNode.h"

using namespace std;
typedef binTreeNode<int> treenode;

void preorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  cout << p->data << " ";
  preorderPrint(p->left);
  preorderPrint(p->right);
}

void inorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  inorderPrint(p->left);
  cout << p->data << " ";
  inorderPrint(p->right);
}

void postorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  postorderPrint(p->left);
  postorderPrint(p->right);
  cout << p->data << " ";
}

void doDrawTree(treenode *p, string lpad, string rpad)
{
  string pad = lpad.substr(0, lpad.size() - 1);
  if (p == 0) return;
  doDrawTree(p->right, rpad + "    |", rpad + "     ");
  cout << pad << "+--" << setw(3) << p->data << endl;
  doDrawTree(p->left,  lpad + "     ", lpad + "    |");
}
void drawTree(treenode *p)
{
  doDrawTree(p, " ", " ");
}

int main()
{

  treenode *root;
  root = new treenode(5);
  root->left = new treenode(3);
  root->right = new treenode(10);
  treenode *p = root->right;
  p->left = new treenode(8);
  p->right = new treenode(15);
  p->left->left = new treenode(7);
  p->left->right = new treenode(9);
  root->left->right = new treenode(4);
  root->left->left = new treenode(1);

  drawTree(root);
  cout << endl;

  cout << "Preorder Traversal:" << endl;
  preorderPrint(root);

  cout << "\nInorder Traversal:" << endl;
  inorderPrint(root);

  cout << "\nPostorder Traversal:" << endl;
  postorderPrint(root);

  return 0;
}