#include <iostream>

using namespace std;

// If we would like to change to something other than storing ints, this
// is where we would do.
#define VAL_TYPE int

// This is the basis of our binary search tree
struct Node
{
  VAL_TYPE val;
  Node* left;
  Node* right;
};

// Return the number of nodes in the tree
unsigned int size(Node* root)
{
  // If the tree is empty, then there is nothing to report
  if (root == NULL) return 0;

  // Otherwise, it is 1 (for the root) plus the size of both sub-trees
  return 1 + size(root->right) + size(root->left);
}

// Find the maximum depth of the tree
unsigned int maxDepth(Node* root)
{
  // If the tree is empty, then there is no depth
  if (root == NULL) return 0;

  // Otherwise, it is 1 layer more than the maximum of the depth of
  // the two subtrees
  return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// find the maximum value in this tree, iteratively.
VAL_TYPE findMaxIter(Node* root)
{
  // The maximum value is the right-most node.  If there was 
  // anything bigger, it would have to be stored in the right-subtree
  // of this node.  So there obviously can't be anything bigger.
  Node* cur = root;
  for (; cur->right != NULL; cur = cur->right) ;
  return cur->val;
}

// find the maximum value in the tree, recursively
VAL_TYPE findMaxRecursive(Node* root)
{
  // If there is no right-subtree, then return this value.
  if (root->right == NULL) return root->val;

  // Otherwise, return the maximum of the right-subtree
  return findMaxRecursive(root->right);
}

// Insert iteratively
Node* insert(Node* root, VAL_TYPE val)
{
  // This is a pointer-to-the-pointer-to the current node.
  // This way we don't have to track whether we are a left-child
  // or a right-child.
  Node** prev = &root;
  Node* cur = root;

  // Now loop until we fall off the tree
  while (cur != NULL)
    {
      // If the value to insert is less than the current value
      if (val < cur->val)
	{
	  // Go left
	  prev = &cur->left;
	  cur = cur->left;
	}
      // Otherwise we are going right
      else
	{
	  prev = &cur->right;
	  cur = cur->right;
	}
    }
  
  // Create the new node
  cur = new Node();
  cur->val = val;
  
  // If prev is NULL, then this is actually insert at the root
  // by simply returning this value.
  if (prev == NULL)
    return cur;
  
  // Otherwise, tweak the last pointer that we followed
  (*prev) = cur;

  // And return the original root, which is still the root.
  return root;
}

// A much simpler insertion
Node* insertRecursive(Node* root, VAL_TYPE val)
{
  // If we are inserting into an empty (sub)tree
  if (root == NULL)
    {
      // Create a new node and return that as the root
      Node* newNode = new Node;
      newNode->val = val;
      newNode->left = NULL;
      newNode->right = NULL;
      return newNode;
    }
  
  // Otherwise, insert into the appropriate subtree
  if (val < root->val) 
    root->left = insertRecursive(root->left, val);
  else 
    root->right = insertRecursive(root->right, val);

  // And return the current node as the root
  return root;
}

bool hasVal(Node* root, VAL_TYPE val)
{
  // Lazy step
  if (root == NULL) return false;

  // Well, now that we are done, I TRUST that this works, and can write
  if (val < root->val) 
    return hasVal(root->left, val);
  else if (val > root->val) 
    return hasVal(root->right, val);
  else // Must be the same
    return true;
}

void deleteTree(Node* root)
{
  // Must be recursive
  if (root == NULL) return;

  deleteTree(root->right);
  deleteTree(root->left);
  delete root;  

}

void PrintSorted(Node* root)
{
  // Must be recursive
  if (root == NULL) return;
  
  PrintSorted(root->left);
  cout << root->val << " ";
  PrintSorted(root->right);
}


int main()
{
  Node* root = NULL;
  root = insert(root, 10);
  root = insert(root, 15);
  root = insert(root, 16);
  root = insert(root, 13);
  root = insert(root, 11);
  root = insert(root, 5);
  root = insert(root, 7);
  root = insert(root, 3);

  // So now the tree should be:
  //           10
  //      5          15
  //   3    7     13     16
  //             11 

  PrintSorted(root);
  cout << endl;
}