#ifndef BST_HPP
#define BST_HPP
#include "BSTNode.hpp"
#include "BSTIterator.hpp"
#include <iostream>

template<typename Data>
class BST {

protected:

  /** Pointer to the root of this BST, or 0 if the BST is empty */
  BSTNode<Data>* root;

  /** Number of Data items stored in this BST. */
  unsigned int isize;

public:

  /** define iterator as an aliased typename for BSTIterator<Data>. */
  typedef BSTIterator<Data> iterator;

  /** Default constructor.
      Initialize an empty BST.
   */
  BST() : root(0), isize(0) {  }


  /** Default destructor.
      Delete every node in this BST.
   */
  delete root;
  virtual ~BST() {

  }

  /** Given a reference to a Data item, insert a copy of it in this BST.
   *  Return  true if the item was added to this BST
   *  as a result of this call to insert,
   *  false if an item equal to this one was already in this BST.
   *  Note: This function should use only the '<' operator when comparing
   *  Data items. (should not use >, <=, >=)
   */ // TODO
  virtual bool insert(const Data& item) {
// create new current node for inserted node
  BSTNode<Data> currNode = root;
  int test = 0;
 // check if there are existing nodes in the tree
   if (root == nullptr)
   { root = new BSTNode<item>;
     return true; }
   else {
// compare current node to existing nodes
   while (currNode && test == 0) {
   if (item < currNode->data) {
  	currNode = currNode->left;
	if (currNode->left == nullptr)
	   currNode->left->parent = currNode;
	   isize++;
	   return true;
	   test = 1;
	}

   if (currNode->data < item) {
   	currNode = currNode.right;
   	if (currNode->right == nullptr)
	   currNode->right->parent = currNode;
	   isize++;
	   return true;
	   test = 1;
	}
   }

  return false;


}



  }


  /** Find a Data item in the BST.
   *  Return an iterator pointing to the item, or pointing past
   *  the last node in the BST if not found.
   *  Note: This function should use only the '<' operator when comparing
   *  Data items. (should not use >, <=, >=)
   */ // TODO
  iterator find(const Data& item) const {
    if (root == null) return false;

    else {
	BSTNode<Data> currNode = root;


  }


  /** Return the number of items currently in the BST.
   */ // TODO
  unsigned int size() const {
	return 0;
  }

  /** Return true if the BST is empty, else false.
   */ // TODO
  bool empty() const {
	return 0;

  }

  /** Empties the Tree
   */ // TODO
  bool clear(){
	return 0;

  }

  /** Return an iterator pointing to the first item in the BST (not the root).
   */ // TODO
  iterator begin() const {
	return 0;

  }

  /** Return an iterator pointing past the last item in the BST.
   */
  iterator end() const {
    return typename BST<Data>::iterator(0);
  }

  /** Perform an inorder traversal of this BST.
   */
  void inorder() const {
    inorder(root);
  }


private:

  /** Recursive inorder traversal 'helper' function */

  /** Inorder traverse BST, print out the data of each node in ascending order.
      Implementing inorder and deleteAll base on the pseudo code is an easy way to get started.
   */ // TODO
  void inorder(BSTNode<Data>* n) const {
    /* Pseudo Code:
      if current node is null: return;
      recursively traverse left sub-tree
      print current node data
      recursively traverse right sub-tree
    */
  }

  /** Find the first element of the BST
   */
  static BSTNode<Data>* first(BSTNode<Data>* root) {
    if(root == 0) return 0;
    while(root->left != 0) root = root->left;
    return root;
  }

  /** do a postorder traversal, deleting nodes
   */ // TODO
  static void deleteAll(BSTNode<Data>* n) {
	return 0;
    /* Pseudo Code:
      if current node is null: return;
      recursively delete left sub-tree
      recursively delete right sub-tree
      delete current node
    */
  }


 };


#endif //BST_HPP