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

/*
This is lab test #5 version 2 for D2 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;
 
  // sumNodesWOddLeft() returns the sum of the of nodes with left children containing odd values.

  cout << "\nIn the following tree, the sum of the nodes with odd left children is (should be 0): " << t1.sumNodesWOddLeft() << ".\n\n";
  t1.display();

  t1.insert(8);
  t1.insert(1);
  t1.insert(10);
  t1.insert(12);
  cout << "\nIn the following tree, the sum of the nodes with odd left children is (should be 8): " << t1.sumNodesWOddLeft() << ".\n\n";
  t1.display();

  t1.insert(9);
  t1.insert(4);
  t1.insert(0);
  cout << "\nIn the following tree, the sum of the nodes with odd left children is (should be 18): " << t1.sumNodesWOddLeft() << ".\n\n\n";
  t1.display();


  // largestIsOdd() returns the true if the largest value in the tree is odd, false otherwise. 
  // Throws overflow_error exception if tree is empty.

  t2.insert(7);
  t2.insert(2);
  if (t2.largestIsOdd())
     cout << "\nCorrect: In the following tree, the largest value is odd.\n";
  else
     cout << "\nIncorrect: In the following tree, the largest value is not odd.\n";
  t2.display();

  t2.insert(8);
  t2.insert(5);
  t2.insert(1);
  if (t2.largestIsOdd())
     cout << "\nIncorrectL In the following tree, the largest value is odd.\n";
  else
     cout << "\nCorrect: In the following tree, the largest value is not odd.\n";
  t2.display();

  t2.insert(81);
  t2.insert(15);
  t2.insert(0);
  if (t2.largestIsOdd())
     cout << "\nCorrect: In the following tree, the largest value is odd.\n";
  else
     cout << "\nIncorrect: In the following tree, the largest value is not odd.\n";
  t2.display();

  if (t1.largestIsOdd())
     cout << "\nIncorrect: In the following tree, the largest value is odd.\n";
  else
     cout << "\nCorrect: In the following tree, the largest value is not odd.\n";
  t1.display();

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


  // deleteGreaterThan(n) deletes all the nodes in the tree containing values larger than n.

  t3.insert(21);
  t3.insert(19);
  t3.deleteGreaterThan(20);
  cout << "\ntree after deleting values greater than 20 (should be 19):\n\n";
  t3.display();

  t3.insert(20);
  t3.insert(41);
  t3.deleteGreaterThan(10);
  cout << "\ntree after deleting values greater than 10 (should be empty):\n\n";
  t3.display();

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

  t4.deleteGreaterThan(1000);
  cout << "\ntree after deleting values greater than 1000 (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;

}