#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 !
/*
 * Notes about scoring:
 *
 * A 100% proper solution must handle all cases:
 * - Works when the tree is empty (root_ == 0)
 * - Works when left subtree is empty (root_->left_ == 0)
 * - Works when right subtree is empty (root_->right_ == 0) 
 * - Works when both right and left subtree exists and place the
     "leftover" subtree in a location that produced a correct tree
     without copying the data stored in any node (only pointer
     operations).
 * - Do no leak memory on the removed node.
 * - Stops ~Tree_Node() from recursively deleting the subtree of the deleted node.
 *
 * A 100% good solution gives 10 points. Any mistake give point
 * reduction. Only serious solution attemts that attempt to fullfil
 * the entire specification give points.
 */
void Tree::remove_root()
{
  if (root_ != 0)
  {
    Tree_Node *tmp = root_;
    Tree_Node *cur = root_->left_;
    if (cur == 0)
    {
      root_= root_->right_;
      tmp->right_ = 0;
      delete tmp;
      return;
    }
    Tree_Node *prev = root_;
    while (cur != 0)
    {
      prev = cur;
      cur = cur->right_;
    }
    
    prev->right_ = root_->right_;
    root_ = root_->left_;
    
    tmp->left_ = 0;
    tmp->right_ = 0;
    delete tmp;
  }
}


// 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;
}