#include "stdstuff.h"
#include "Tree.h"

/*
This is lab test #5 version 1 for D1 with TA tests.

In this test you are to extend the tree class provided (Tree.h and Tree.cpp on the G: drive).

You are to add the three missing methods to the Tree class.  

Running the sample executable and examining the test code below
should give the general idea.

Note that your code must work in all cases, not just for the examples below.

Your solutions may be iterative or recursive, as you choose.

Your code must take advantage of the fact that the tree is sorted, if appropriate.
(For example, you would never find the largest value in a sorted tree in the left sub-tree.)

You may write additional private member methods and helper functions, if required.  

You may use other methods in the Tree class.

Submit files Tree.h and Tree.cpp using the submit program provided.
*/


void realMain () {

  Tree t1, t2, t3, t4;
 
  // countNodesWEvenRight() returns the number of nodes with right children containing even values.

  cout << "\nIn the following tree, the number of nodes with even right children is (should be 0): " << t1.countNodesWEvenRight() << ".\n\n";
  t1.display();

  t1.insert(7);
  t1.insert(2);
  t1.insert(9);
  t1.insert(12);
  cout << "\nIn the following tree, the number of nodes with even right children is (should be 1): " <<   t1.countNodesWEvenRight() << ".\n\n";
  t1.display();

  t1.insert(8);
  t1.insert(4);
  t1.insert(1);
  cout << "\nIn the following tree, the number of nodes with even right children is (should be 2): " <<   t1.countNodesWEvenRight() << ".\n\n\n";
  t1.display();


  // findSmallest() returns the smallest value in the tree.  Throws overflow_error exception if tree is empty.

  t2.insert(7);
  t2.insert(2);
  cout << "\nIn the following tree, the smallest value is (should be 2) : " << t2.findSmallest() << ".\n\n";
  t2.display();

  t2.insert(8);
  t2.insert(5);
  t2.insert(1);
  cout << "\nIn the following tree, the smallest value is (should be 1):  " << t2.findSmallest() << ".\n\n";
  t2.display();

  t2.insert(81);
  t2.insert(15);
  t2.insert(0);
  cout << "\nIn the following tree, the smallest value is (should be 0):  " << t2.findSmallest() << ".\n\n";
  t2.display();

  cout << "\nIn the following tree, the smallest value is (should be 1):  " << t1.findSmallest() << ".\n\n";
  t1.display();

  try {
    cout << "\nIncorrect: In the following tree, the smallest value is:  " << t3.findSmallest() << ".\n\n";
  } catch (overflow_error &e) { 
    cout << "\nCorrect: overflow_error exception <" << e.what() << "> occurred finding smallest in:\n";
    t3.display();
  }


  // deleteOddValues() deletes all the nodes in the tree containing odd values.

  t3.insert(21);
  t3.insert(19);
  t3.deleteOddValues();
  cout << "\ntree after deleting odd values (should be empty):\n\n";
  t3.display();

  t3.insert(20);
  t3.insert(41);
  t3.deleteOddValues();
  cout << "\ntree after deleting odd values (should be 20):\n";
  t3.display();

  t3.insert(9);
  t3.insert(12);
  t3.insert(11);
  t3.insert(10);
  t3.deleteOddValues();
  cout << "\ntree after deleting odd values (should be 20, 12, 10):\n";
  t3.display();

  t4.deleteOddValues();
  cout << "\ntree after deleting odd values (should be empty):\n";
  t4.display();
  cout << "\n";
}



int main () {

  try {

    realMain ();

  }
  catch (exception &e) { // catches all uncaught exceptions

    cout << "\nException <" << e.what() << "> occurred.\n";

  }

  pause ();
  return 0;

}