// Lab Problem T11.1

// CS211 ADS2

// T Naughton, CS NUIM

#include<iostream>

#include<string>



/* A class to maintain an ordered list of integers.

** The following methods are supported:

** -OrdIntTree::Add // Add an int to the tree at an appropriate pos

** -OrdIntTree::Delete // Delete the entire tree

** -OrdIntTree::PrintTree // Print the tree structure on its side

** -OrdIntTree::Remove // Remove an element from the tree

** -OrdIntTree::MinData // The minimum data value in the tree

** -OrdIntTree::PrintPaths // Print the paths from root to each leaf

*/



class BinTreeNode {

  // A very simple class describing each node of the binary tree

 public:

  int data; // data held at each node

  BinTreeNode * left; // pointer to left subtree

  BinTreeNode * right; // pointer to right subtree

};



class OrdIntTree {



  BinTreeNode * root; // a pointer to the root of the tree



 public:

  OrdIntTree(); // constructor

  ~OrdIntTree(); // destructor

  void SetRoot(BinTreeNode * ptr);

  BinTreeNode * GetRoot();



  // Wrapper methods that take

  // care of special cases or extra tasks before calling the

  // private recursive methods that do the real work)

  void Delete(); // delete the entire tree

  void Add(int newdata); // add a new element to the tree such that children

                         // to the left of a parent have lower integers and

                         // children to the right have higher or equal integers.

  void PrintTree(bool info); // Print the tree structure on its side

  void Remove(int sdata); // Remove a given element from the tree whilst

                          // maintaining an ordered list of integers in the tree.

  int MinData(BinTreeNode * current); // Return the min data element in a subtree

  void PrintPaths(); // Print the paths from root to each leaf



 private:

  // recursive implementations of the tasks

  void DeleteRec(BinTreeNode * current);

  void AddRec(BinTreeNode * current, int newdata);

  void PrintTreeRec(BinTreeNode * current, int depth, bool info);

  int Height(BinTreeNode * current);

  int Max(int a, int b);

  bool RemoveRec(BinTreeNode ** current, int sdata);

  void RemoveMinRec(BinTreeNode ** current);

  void PrintPathsRec(BinTreeNode * current, string path);

};



OrdIntTree::OrdIntTree(){

  root = NULL; // Initialise the tree (set root to NULL).

}



OrdIntTree::~OrdIntTree(){

  Delete();

}



void OrdIntTree::SetRoot(BinTreeNode * ptr){

  root = ptr;

}



BinTreeNode * OrdIntTree::GetRoot(){

  return root;

}



void OrdIntTree::Delete(){

  // Wrapper method to delete a tree.

  // Although all memory (including that at the root of the tree) will

  // be deallocated correctly, we should also point the root pointer

  // away from this memory location. This means we can safely add new

  // nodes after deleting the tree

  DeleteRec(GetRoot());

  SetRoot(NULL);

}



void OrdIntTree::DeleteRec(BinTreeNode * current){

  // Recursive method to delete a tree. Deletes nodes from the leaves

  // to the root. Starts at rightmost node of lowest leftmost subtree

  if (current != NULL) {

    DeleteRec(current->left);

    DeleteRec(current->right);

    delete current;

  }

}



void OrdIntTree::Add(int newdata){

  // Wrapper method for adding a node to the tree. The new integer is

  // positioned such that children to the left of a parent have lower

  // int values and children to the right have higher or equal int values.

  // This wrapper takes account of the special case where root==NULL before

  // calling the recursive method

  BinTreeNode * temp;



  if (GetRoot() == NULL) {

    temp = new BinTreeNode;

    temp->data = newdata;

    temp->left = NULL;

    temp->right = NULL;

    SetRoot(temp);



  } else {

    AddRec(GetRoot(), newdata);

  }

}



void OrdIntTree::AddRec(BinTreeNode * current, int newdata){

  // Recursive method for adding a node to the tree. The new integer is

  // positioned such that children to the left of a parent have lower

  // int values and children to the right have higher or equal int values.

  // A wrapper method ensures that current is not NULL

  BinTreeNode * temp;



  if (newdata < current->data) {

    // position to the left of current

    if (current->left == NULL) {

      temp = new BinTreeNode;

      temp->data = newdata;

      temp->left = NULL;

      temp->right = NULL;

      current->left = temp;

    } else {

      AddRec(current->left, newdata);

    }

  } else {

    //position to the right of current

    if (current->right == NULL) {

      temp = new BinTreeNode;

      temp->data = newdata;

      temp->left = NULL;

      temp->right = NULL;

      current->right = temp;

    } else {

      AddRec(current->right, newdata);

    }

  }

}



void OrdIntTree::PrintTree(bool info){

  // Wrapper method for printing the tree structure on its side. Option

  // to include node depths & heights

  cout << "\nHere is the tree:";

  PrintTreeRec(root, 0, info);

}



void OrdIntTree::PrintTreeRec(BinTreeNode * current, int depth, bool info){

  // Print the tree structure on its side. Include symbols to indicate

  // whether a node has a left child (/), a right child (\), or two

  // children (^). Option to include node depths & heights

  int count;

  if (current != NULL) {

    PrintTreeRec(current->right, depth + 1, info);

    cout << endl;

    count = 0;

    while (count < (depth * (info ? 8 : 3))) {

      cout << ' ';

      count++;

    }

    if (info) {

      cout << current->data;

      cout << '(' << depth << ',' << Height(current) << ')';

    } else {

      cout << current->data;

    }

    if ((current->left != NULL) && (current->right != NULL)) {

      cout << '<';

    } else if (current->left != NULL) {

      cout << '\\';

    } else if (current->right != NULL) {

      cout << '/';

    } else {

      // nothing for leaves

    }

    PrintTreeRec(current->left, depth + 1, info);

  }

}



int OrdIntTree::Height(BinTreeNode * current){

  // Return the height of the node

  if (current == NULL) {

    return 0;

  } else if ((current->left == NULL) && (current->right == NULL)) {

    return 0;

  } else {

    return (1 + Max(Height(current->left), Height(current->right)));

  }

}



int OrdIntTree::Max(int a, int b){

  // Return the maximum of two integers

  if (a >= b) {

    return a;

  } else {

    return b;

  }

}



void OrdIntTree::Remove(int sdata){

  // Wrapper method for removing all nodes having a particular data value.

  // The recursive method will be called iteratively until no further such

  // data values are found

  while (RemoveRec(&root, sdata)) {

    //keep removing elements

  }

}



bool OrdIntTree::RemoveRec(BinTreeNode ** current, int sdata){

  // Recursive method to remove a node containing 'sdata' from the tree. The

  // five cases are: empty tree, sdata less than current->data, sdata greater

  // than current->data, sdata equal to current->data where current has two

  // children, and sdata equal to current->data where current has less than

  // two children. The address of 'current' is passed to avoid the need to

  // explicitly keep track of current's parent. Return true if a node has

  // deleted, otherwise false

  BinTreeNode * temp;

  if (*current == NULL) {

    return false;

  } else if (sdata < (*current)->data) {

    RemoveRec(&(*current)->left, sdata);

  } else if (sdata > (*current)->data) {

    RemoveRec(&(*current)->right, sdata);

  } else if (((*current)->left != NULL) && ((*current)->right != NULL)) {

    // two subtrees

    (*current)->data = MinData((*current)->right);

    RemoveMinRec(&(*current)->right);

    return true;

  } else {

    // one or zero subtrees

    temp = *current;

    if ((*current)->left != NULL) {

      *current = (*current)->left;

    } else {

      *current = (*current)->right;

    }

    delete temp;

    return true;

  }

}



int OrdIntTree::MinData(BinTreeNode * current){

  // Return the minimum data element of a given subtree

  if (current == NULL) {

    cout << "\nError: tree is empty.";

  } else if (current->left == NULL) {

    return current->data;

  } else {

    return MinData(current->left);

  }

}



void OrdIntTree::RemoveMinRec(BinTreeNode ** current){

  // Remove the node containing the minimum data value of a given

  // subtree. The address of 'current' is passed to avoid the need

  // to explicitly keep track of current's parent

  BinTreeNode * temp;

  if (*current == NULL) {

    cout << "\nError: no min to delete.";

  } else if ((*current)->left == NULL) {

    temp = *current;

    *current = (*current)->right;

    delete temp;

  } else {

    RemoveMinRec(&(*current)->left);

  }

}



void OrdIntTree::PrintPaths(){

  cout << "\nLeaf paths are ";

  PrintPathsRec(root, "");

}



void OrdIntTree::PrintPathsRec(BinTreeNode * current, string path){

  if (current == NULL) {

    // do nothing

  } else if ((current->left == NULL) && (current->right == NULL)) {

    cout << current->data << ':' << path << ' ';

  } else {

    PrintPathsRec(current->left, path + '0');

    PrintPathsRec(current->right, path + '1');

  }

}



void main(void){



  OrdIntTree tree;



  cout << endl << endl;



  tree.Add(5);

  tree.Add(3);

  tree.Add(7);

  tree.Add(4);

  tree.Add(9);

  tree.Add(11);

  tree.Add(2);

  tree.Add(8);

  tree.Add(1);

  tree.Add(6);

  tree.Add(10);



  tree.PrintTree(false);

  tree.PrintTree(true);

  tree.PrintPaths();

}

/*

Here is the tree:

         11\

            10

      9<

         8

   7<

      6

5<

      4

   3<

      2\

         1

Here is the tree:

                        11(3,1)\

                                10(4,0)

                9(2,2)<

                        8(3,0)

        7(1,3)<

                6(2,0)

5(0,4)<

                4(2,0)

        3(1,2)<

                2(2,1)\

                        1(3,0)

Leaf paths are 1:000 4:01 6:10 8:110 10:1110

*/