// Bst.h
// 	a binary search tree that will contain
// 	all dictionary words for a particular letter
//	there will be 26 of these
//	some may be empty (no dictionary words beginning
//	with 'x', for example)

#ifndef BST_CLASS
#define BST_CLASS

#include <string>
#include "Entry.h"

class Bst {

    char letter;	// letter that all words in this BST begin with
    Entry* root;	// root of this BST

  public:
    // default constructor
    // initializes letter and root
    Bst();

    // indicates which letter all words in the tree begin with 
    Bst(char);

    // copy constructor
    // makes a copy of "other"
    // calls copy()
    Bst(const Bst & other);

    // destructor
    // calls makeEmpty()
    ~Bst();

    // explicitly defined assignment operator
    Bst & operator=(const Bst &);

    // returns the letter with which all words in the BST begin
    char getLetter();

    // returns a pointer to the root (for ConstIterator class)
    Entry * getRootPointer();

    // returns true if word is in Bst
    // MUST BE RECURSIVE
    bool exists(std::string word);

    // searches for word, parent ends up pointing to the 
    // word's parent
    bool search(std::string word, Entry*& parent, Entry *& curr);

    // adds the word if it is not already in the tree
    bool add(std::string);

    // deletes the NODE containing 'word' from the tree
    // you must use one of the methods we have 
    // provided in class
    bool erase(std::string word);

    // does a preorder traversal of the tree
    // may call helper function
    // MUST BE RECURSIVE
    void preorder();

    // does an inorder traversal of the tree
    // may call helper function
    // MUST BE RECURSIVE
    void inorder();

    // does a postorder traversal of the tree
    // may call helper function
    // MUST BE RECURSIVE
    void postorder();

    // prints the BST in alphabetical order
    // MUST BE RECURSIVE
    void print();

    // deletes all nodes in the tree
    // sets root to NULL
    // MUST BE RECURSIVE
    void makeEmpty(Entry* curr);

  private:

    void copy(Entry *, Entry *);

    // YOU MAY WRITE ANY OTHER PRIVATE FUNCTIONS THAT YOU NEED
};

#endif // BST_CLASS