#include <iostream>
#include <iomanip>

using namespace std;

#include "Tree.h"

// Representation of one Node in the tree
struct Tree_Node
{
  Tree_Node(int data, Tree_Node * left = 0, Tree_Node * right = 0)
    : data_(data), left_(left), right_(right)
  {}
  
  ~Tree_Node()
  {
    delete left_;
    delete right_;
    left_  = 0;
    right_ = 0;
  }

  int data_;
  Tree_Node * left_;
  Tree_Node * right_;
};

// YOUR CODE HERE: Implement remove_root !


// Insert adds a value as a leaf in the tree.
// If the value to insert already exists insert does nothing.
void Tree::insert(int data, Tree_Node *& tree)
{
  if (tree == 0)
  {
    tree = new Tree_Node(data);
  }
  else if (tree->data_ > data)
  {
    insert(data, tree->left_);
  }
  else if (tree->data_ < data)
  {
    insert(data, tree->right_);
  }
}

void Tree::insert(int data)
{
  insert(data, root_);
}

// Print will display the tree. If you tilt your head 90 degree to
// your left you will see the tree with the root at "top" (to the left
// side of screen. Note that the spacing is not perfect, and it can be
// confusing to see which node that is childnode of which
// sometimes. Draw what you expect on paper to compare.
void Tree::print(ostream &os, const Tree_Node * tree, int indent) const
{
  if (tree == 0) return; // Ignore empty trees.

  if (tree->right_ != 0) // Visit right subtree first if it's there.
  {
    print(os,tree->right_, indent+2);
    cout << setw(indent+1) << '/' << endl;
  }
  
  cout << setw(indent) << tree->data_ << endl; // Display current node.

  if (tree->left_ != 0) // Visit left subtree if it's there.
  {
    cout << setw(indent+1) << '\\' << endl;
    print(os,tree->left_, indent+2);
  }
}

void Tree::print(ostream &os, int indent) const
{
  print(os,root_,indent);
}

// Member returns true if the searched for data exists in the tree.
bool Tree::member(int data, const Tree_Node * tree) const
{
  if (tree == 0)
  {
    return false;
  }
  else if (tree->data_ == data)
  {
    return true;
  }
  else if (tree->data_ > data)
  {
    return member(data, tree->left_);
  }
  return member(data, tree->right_);
}

bool Tree::member(int data) const
{
  return member(data, root_);
}

// Clear will recursively delete the entire tree by calling the
// destructor on the root node. After this all nodes are invalid to
// use, so the tree is set to be empty.
void Tree::clear()
{
  delete root_;
  root_ = 0;
}

// Is_empty returns true if the tree is empty.
bool Tree::empty() const
{
  return root_ == 0;
}