#include <iostream>
#include <string>

using namespace std;

// functions are called ppbtodN: (p)rint (p)erfect (b)inary (t)ree (o)f (d)epth (Number)

// RULE 1:
//   the only thing ppbtodN has to do is to print all the data in the tree it is given,
//   in ascending order.

// No need to check anything. Assume it is somehow guaranteed that ppbtod4 will only
// ever be given perfect binary trees of depth 4

struct node
{ string data;
  node * left, * right; };

// RULE 2:
//   every node has one piece of data. All data reachable through the left pointer will be
//   less than (alphabetically before) this piece of data. All data reachable through the
//   right pointer will be more than (alphabetically after) this node's piece of data.

void ppbtod0(node * t)
{ }

// if the two rules have been obeyed, ppbtod0 will do exactly what it is meant to do.

// observe that at the root of a perfect binary tree of depth 4 (just for example) the
// left pointer points to a perfect binary tree of depth 3 (all of whose data items
// belong before the root's data) and the right pointer points to another perfect binary
// tree of depth 3 (all of whose data items belong after the root's data).


void ppbtod1(node * t)
{ ppbtod0(t->left);
  cout << t->data;
  ppbtod0(t->right); }

// at depth 1 we know both subtrees have depth 0 so ppbtod0 will print them correctly
// so rule 2 means ppbtod1 must also print its tree correctly


void ppbtod2(node * t)
{ ppbtod1(t->left);
  cout << t->data;
  ppbtod1(t->right); }

// at depth 2 we know both subtrees have depth 1 so ppbtod1 will print them correctly
// so rule 2 means ppbtod2 must also print its tree correctly


void ppbtod3(node * t)
{ ppbtod2(t->left);
  cout << t->data;
  ppbtod2(t->right); }

// at depth 3 we know both subtrees have depth 2 so ppbtod2 will print them correctly
// so rule 2 means ppbtod3 must also print its tree correctly


void ppbtod4(node * t)
{ ppbtod3(t->left); 
  cout << t->data;
  ppbtod3(t->right); }

// at depth 4 we know both subtrees have depth 3 so ppbtod3 will print them correctly
// so rule 2 means ppbtod4 must also print its tree correctly


void ppbtod5(node * t)
{ ppbtod4(t->left);
  cout << t->data;
  ppbtod4(t->right); }


// at depth 5 we know both subtrees have depth 4 so ppbtod4 will print them correctly
// so rule 2 means ppbtod5 must also print its tree correctly

// etc.

// What if the trees are not perfect? pbtodN will print a binary tree whose depth is
// less than OR EQUAL to N.

// It needs to check something. Whenever a pointer is followed, e.g. t->left, t->data,
// or t->right, we must be certain that it (t) can not possibly be NULL. That was not
// needed before because the definition of ppbtodN guaranteed that none of the functions
// except number 0 will ever receive a NULL parameter.


void pbtod0(node * t)
{ }


void pbtod1(node * t)
{ if (t != NULL)
  { pbtod0(t->left);
    cout << t->data;
    pbtod0(t->right); } }


void pbtod2(node * t)
{ if (t != NULL)
  { pbtod1(t->left);
    cout << t->data;
    pbtod1(t->right); } }


void pbtod3(node * t)
{ if (t != NULL)
  { pbtod2(t->left);
    cout << t->data;
    pbtod2(t->right); } }


void pbtod4(node * t)
{ if (t != NULL)
  { pbtod3(t->left);
    cout << t->data;
    pbtod3(t->right); } }


void pbtod5(node * t)
{ if (t != NULL)
  { pbtod4(t->left);
    cout << t->data;
    pbtod4(t->right); } }


// What is the difference between all of the new pbtodN functions excluding pbtod0?
// Almost nothing, just the names.

// So I could make the one part of the name that can be different into a parameter:


void pbtod(int depth, node * t)
{ if (t != NULL)
  { pbtod(depth - 1, t->left);
    cout << t->data;
    pbtod(depth - 1, t->right); } }


// Notice that the new parameter is never used. It is passed on, slightly modifed,
// to the functions that are called, but never actually used for anything.

// If something is never used, obviously we don't need it:


void pbt(node * t)
{ if (t != NULL)
  { pbt(t->left);
    cout << t->data;
    pbt(t->right); } }


// That is exactly the normal tree printing function.