bst.h

#ifndef BST_H
#define BST_H

#include <iostream>
#include <exception>
#include <cstdlib>
#include <utility>

/**
 * A templated class for a Node in a search tree.
 * The getters for parent/left/right are virtual so
 * that they can be overridden for future kinds of
 * search trees, such as Red Black trees, Splay trees,
 * and AVL trees.
 */
template <typename Key, typename Value>
class Node
{
public:
    Node(const Key& key, const Value& value, Node<Key, Value>* parent);
    virtual ~Node();

    const std::pair<const Key, Value>& getItem() const;
    std::pair<const Key, Value>& getItem();
    const Key& getKey() const;
    const Value& getValue() const;
    Value& getValue();

    virtual Node<Key, Value>* getParent() const;
    virtual Node<Key, Value>* getLeft() const;
    virtual Node<Key, Value>* getRight() const;

    void setParent(Node<Key, Value>* parent);
    void setLeft(Node<Key, Value>* left);
    void setRight(Node<Key, Value>* right);
    void setValue(const Value &value);

//protected:
    std::pair<const Key, Value> item_;
    Node<Key, Value>* parent_;
    Node<Key, Value>* left_;
    Node<Key, Value>* right_;
};

/*
  -----------------------------------------
  Begin implementations for the Node class.
  -----------------------------------------
*/

/**
* Explicit constructor for a node.
*/
template<typename Key, typename Value>
Node<Key, Value>::Node(const Key& key, const Value& value, Node<Key, Value>* parent) :
    item_(key, value),
    parent_(parent),
    left_(nullptr),
    right_(nullptr)
{

}

/**
* Destructor, which does not need to do anything since the pointers inside of a node
* are only used as references to existing nodes. The nodes pointed to by parent/left/right
* are freed by the BinarySearchTree.
*/
template<typename Key, typename Value>
Node<Key, Value>::~Node()
{

}

/**
* A const getter for the item.
*/
template<typename Key, typename Value>
const std::pair<const Key, Value>& Node<Key, Value>::getItem() const
{
    return item_;
}

/**
* A non-const getter for the item.
*/
template<typename Key, typename Value>
std::pair<const Key, Value>& Node<Key, Value>::getItem()
{
    return item_;
}

/**
* A const getter for the key.
*/
template<typename Key, typename Value>
const Key& Node<Key, Value>::getKey() const
{
    return item_.first;
}

/**
* A const getter for the value.
*/
template<typename Key, typename Value>
const Value& Node<Key, Value>::getValue() const
{
    return item_.second;
}

/**
* A non-const getter for the value.
*/
template<typename Key, typename Value>
Value& Node<Key, Value>::getValue()
{
    return item_.second;
}

/**
* An implementation of the virtual function for retreiving the parent.
*/
template<typename Key, typename Value>
Node<Key, Value>* Node<Key, Value>::getParent() const
{
    return parent_;
}

/**
* An implementation of the virtual function for retreiving the left child.
*/
template<typename Key, typename Value>
Node<Key, Value>* Node<Key, Value>::getLeft() const
{
    return left_;
}

/**
* An implementation of the virtual function for retreiving the right child.
*/
template<typename Key, typename Value>
Node<Key, Value>* Node<Key, Value>::getRight() const
{	
	//std::cout << " Right child: " << right_ <<std::endl;
    return right_;
}

/**
* A setter for setting the parent of a node.
*/
template<typename Key, typename Value>
void Node<Key, Value>::setParent(Node<Key, Value>* parent)
{
    parent_ = parent;
}

/**
* A setter for setting the left child of a node.
*/
template<typename Key, typename Value>
void Node<Key, Value>::setLeft(Node<Key, Value>* left)
{
    left_ = left;
}

/**
* A setter for setting the right child of a node.
*/
template<typename Key, typename Value>
void Node<Key, Value>::setRight(Node<Key, Value>* right)
{
    right_ = right;
}

/**
* A setter for the value of a node.
*/
template<typename Key, typename Value>
void Node<Key, Value>::setValue(const Value& value)
{
    item_.second = value;
}

/*
  ---------------------------------------
  End implementations for the Node class.
  ---------------------------------------
*/

/**
* A templated unbalanced binary search tree.
*/
template <typename Key, typename Value>
class BinarySearchTree
{
public:
    BinarySearchTree(); //TODO
    virtual ~BinarySearchTree(); //TODO
    virtual void insert(const std::pair<const Key, Value>& keyValuePair); //TODO
    virtual void remove(const Key& key); //TODO
    void clear(); //TODO
    bool isBalanced() const; //TODO
    void print() const;
    bool empty() const;

    template<typename PPKey, typename PPValue>
    friend void prettyPrintBST(BinarySearchTree<PPKey, PPValue> & tree);
public:
    /**
    * An internal iterator class for traversing the contents of the BST.
    */
    class iterator  // TODO
    {
    public:
        iterator();

        std::pair<const Key,Value>& operator*() const;
        std::pair<const Key,Value>* operator->() const;

        bool operator==(const iterator& rhs) const;
        bool operator!=(const iterator& rhs) const;

        iterator& operator++();

    protected:
        friend class BinarySearchTree<Key, Value>;
        iterator(Node<Key,Value>* ptr);
        Node<Key, Value> *current_;
    };

public:
    iterator begin() const;
    iterator end() const;
    iterator find(const Key& key) const;
    Value& operator[](const Key& key);
    Value const & operator[](const Key& key) const;

protected:
    // Mandatory helper functions
    Node<Key, Value>* internalFind(const Key& k) const; // TODO
    Node<Key, Value> *getSmallestNode() const;  // TODO
    static Node<Key, Value>* predecessor(Node<Key, Value>* current); // TODO
    // Note:  static means these functions don't have a "this" pointer
    //        and instead just use the input argument.

    // Provided helper functions
    virtual void printRoot (Node<Key, Value> *r) const;
    virtual void nodeSwap( Node<Key,Value>* n1, Node<Key,Value>* n2) ;

    // Add helper functions here
    static Node<Key, Value>* successor(Node<Key, Value>* current);
    void clearHelper(Node<Key, Value> *r);
    int calculateHeightIfBalanced(Node<Key, Value> * root) const;
		bool isBalancedHelper(Node<Key, Value> *root) const;
	  //Node<Key, Value> *getLargestNode();


protected:
    Node<Key, Value>* root_;
    // You should not need other data members
};

/*
--------------------------------------------------------------
Begin implementations for the BinarySearchTree::iterator class.
---------------------------------------------------------------
*/

/**
* Explicit constructor that initializes an iterator with a given node pointer.
*/
template<class Key, class Value>
BinarySearchTree<Key, Value>::iterator::iterator(Node<Key,Value> *ptr) : current_(ptr){}
//Use init. list to set the funtion arguemnt as the current Node that the iterator is pointing to

/**
* A default constructor that initializes the iterator to nullptr.
*/
template<class Key, class Value>
BinarySearchTree<Key, Value>::iterator::iterator()  : current_(nullptr){}
//Set the iterator to nullptr

/**
* Provides access to the item.
*/
template<class Key, class Value>
std::pair<const Key,Value> &
BinarySearchTree<Key, Value>::iterator::operator*() const
{
    return current_->getItem();
}

/**
* Provides access to the address of the item.
*/
template<class Key, class Value>
std::pair<const Key,Value> *
BinarySearchTree<Key, Value>::iterator::operator->() const
{
    return &(current_->getItem());
}

/**
* Checks if 'this' iterator's internals have the same value
* as 'rhs'
*/
template<class Key, class Value>
bool
BinarySearchTree<Key, Value>::iterator::operator==(
    const BinarySearchTree<Key, Value>::iterator& rhs) const
{
    //'This' is a pointer to an iterator that points to a Node in the BST. Compare
    //the pair that each iterator ponits to
    return(current_ == rhs.current_);
}

/**
* Checks if 'this' iterator's internals have a different value
* as 'rhs'
*/
template<class Key, class Value>
bool
BinarySearchTree<Key, Value>::iterator::operator!=(
    const BinarySearchTree<Key, Value>::iterator& rhs) const
{
    return(current_ != rhs.current_);
}


/**
* Advances the iterator's location using an in-order sequencing
*/
template<class Key, class Value>
typename BinarySearchTree<Key, Value>::iterator&
BinarySearchTree<Key, Value>::iterator::operator++()
{   //Assume that curerent node has been visited in proper order

    //Create an iterator from the successor 
    BinarySearchTree<Key, Value>::iterator fin(successor(current_));
    *this = fin;   
    return *this;

}


/*
-------------------------------------------------------------
End implementations for the BinarySearchTree::iterator class.
-------------------------------------------------------------
*/

/*
-----------------------------------------------------
Begin implementations for the BinarySearchTree class.
-----------------------------------------------------
*/

/**
* Default constructor for a BinarySearchTree, which sets the root to nullptr.
*/
template<class Key, class Value>
BinarySearchTree<Key, Value>::BinarySearchTree() : root_(nullptr){}

template<typename Key, typename Value>
BinarySearchTree<Key, Value>::~BinarySearchTree()
{
  clear();
}

/**
 * Returns true if tree is empty
*/
template<class Key, class Value>
bool BinarySearchTree<Key, Value>::empty() const
{
    return root_ == nullptr;
}

template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::print() const
{
    printRoot(root_);
    std::cout << "\n";
}

/**
* Returns an iterator to the "smallest" item in the tree
*/
template<class Key, class Value>
typename BinarySearchTree<Key, Value>::iterator
BinarySearchTree<Key, Value>::begin() const
{
    BinarySearchTree<Key, Value>::iterator begin(getSmallestNode());
    return begin;
}

/**
* Returns an iterator whose value means INVALID
*/
template<class Key, class Value>
typename BinarySearchTree<Key, Value>::iterator
BinarySearchTree<Key, Value>::end() const
{
    BinarySearchTree<Key, Value>::iterator end(nullptr);
    return end;
}

/**
* Returns an iterator to the item with the given key, k
* or the end iterator if k does not exist in the tree
*/
template<class Key, class Value>
typename BinarySearchTree<Key, Value>::iterator
BinarySearchTree<Key, Value>::find(const Key & k) const
{
    Node<Key, Value> *curr = internalFind(k);
    BinarySearchTree<Key, Value>::iterator it(curr);
    return it;
}

/**
 * @precondition The key exists in the map
 * Returns the value associated with the key
 */
template<class Key, class Value>
Value& BinarySearchTree<Key, Value>::operator[](const Key& key)
{
    Node<Key, Value> *curr = internalFind(key);
    if(curr == nullptr) throw std::out_of_range("Invalid key");
    return curr->getValue();
}
template<class Key, class Value>
Value const & BinarySearchTree<Key, Value>::operator[](const Key& key) const
{
    Node<Key, Value> *curr = internalFind(key);
    if(curr == nullptr) throw std::out_of_range("Invalid key");
    return curr->getValue();
}

/**
* An insert method to insert into a Binary Search Tree.
* The tree will not remain balanced when inserting.
* Recall: If key is already in the tree, you should 
* overwrite the current value with the updated value.
*/
template<class Key, class Value>
void BinarySearchTree<Key, Value>::insert(const std::pair<const Key, Value> &keyValuePair)
{
	//Keep comparing with node values until you become a leaf

	if(root_ == nullptr){//If BST is empty
        root_ = new Node<Key, Value>(keyValuePair.first, keyValuePair.second, nullptr);
        return;
	}
	Node<Key, Value>* temp = root_;
	//Make a node pointer from &keyValuePair

	while(1){
        if( temp->getKey() > keyValuePair.first ){//If temp's key is less than new node's key
            if(temp->getLeft() != nullptr){//If there is a left child
                temp = temp->getLeft();//Set temp to left child
            }else{//Set it as child				
                Node<Key, Value>* newNode = new  Node<Key, Value>(keyValuePair.first, keyValuePair.second, temp);
                temp->setLeft(newNode);//Set the current node as the parent of the new node
                break;
            }
        }else if(temp->getKey() < keyValuePair.first ){
            if(temp->getRight() != nullptr){//Look at right child
                temp = temp->getRight();
            }else{//Set it as child						
                Node<Key, Value>* newNode = new  Node<Key, Value>(keyValuePair.first, keyValuePair.second, temp);
                temp->setRight(newNode);
                break;
            }
        }else{
                temp->setValue(keyValuePair.second);//Change the value of the Node with the same key
                break;
        }
	}
}


/**
* A remove method to remove a specific key from a Binary Search Tree.
* Recall: The writeup specifies that if a node has 2 children you
* should swap with the predecessor and then remove.
*/
template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::remove(const Key& key)
{
	//BC - empty tree
	if(root_ == nullptr){
		return;
	}

	Node<Key, Value>* nI = internalFind(key);

	//If node is not in tree
	if(nI == nullptr){
		return;
	}

	//Get node's parent
	Node<Key, Value>* pni = nI->getParent();

	//Leaf node
	if(nI->getRight() == nullptr && nI->getLeft() == nullptr){
		if( nI == root_){//only one node in tree
			delete root_;
			root_ = nullptr;
			return;
		}

		if(pni->getLeft() == nI){
			pni->setLeft(nullptr);
		}else{
			pni->setRight(nullptr);
		}

		delete nI;
		nI = nullptr;

	//Only left Child
	}else if(nI->getLeft() != nullptr && nI->getRight() == nullptr){
		if(nI == root_){//If left subtree has only one node
			root_ = nI->getLeft();
			root_->setParent(nullptr);
			delete nI;
			nI = nullptr;
			return;
		}
		
		if(pni->getLeft() == nI){
			pni->setLeft(nI->getLeft());
		}else{
			pni->setRight(nI->getLeft());
		}
		nI->getLeft()->setParent(pni);
		delete nI;
		nI = nullptr;

	//Only Right Child
	}else if(nI->getLeft() == nullptr && nI->getRight() != nullptr){
		if(nI == root_){
			root_ = nI->getRight();
			root_->setParent(nullptr);
			delete nI;
			nI = nullptr;
			return;
		}
		
		if(pni->getLeft() == nI){
			pni->setLeft(nI->getRight());
		}else{
			pni->setRight(nI->getRight());
		}
		nI->getRight()->setParent(pni);
		delete nI;
		nI = nullptr;

	//Two children
	}else{
		//Swap with predecessor
		nodeSwap(nI,predecessor(nI));

		Node<Key, Value>* pni = nI->getParent();


		//If predecessor was leaf node
		if(nI->getRight() == nullptr && nI->getLeft() == nullptr){
			if(pni->getLeft() == nI){
				pni->setLeft(nullptr);
			}else{
				pni->setRight(nullptr);
			}

			delete nI;
			nI = nullptr;

		//If predecessor has a (left) child 
		}else{//Was predecessor a right child or left child?
			if(pni->getLeft() == nI){
				pni->setLeft(nI->getLeft());
			}else{
				pni->setRight(nI->getLeft());
			}
			nI->getLeft()->setParent(pni);
			delete nI;
			nI = nullptr;
		}
	}
}



template<class Key, class Value>
Node<Key, Value>*
BinarySearchTree<Key, Value>::predecessor(Node<Key, Value>* current)
{
    //predecessor - the right most value of the left subtree
    //Traverse right subtree of left child until you reach a leaf
    current = current->getLeft();

    if(current != nullptr){    

        while(current->getRight() != nullptr){
            current = current->getRight();
        }

    }else{

        while(current < current->getParent()){
            current = current->getParent();//Go to parent
            if(current == nullptr){
                //BinarySearchTree<Key, Value>::iterator end(nullptr);
                return nullptr;//If parent doesn't exit (root) return nullptr
            }
        }
        current = current->getParent();

    }

    return current;
}

template<class Key, class Value>
Node<Key, Value>*
BinarySearchTree<Key, Value>::successor(Node<Key, Value>* current){
    if(current->getRight() != nullptr){   
        current = current->getRight(); 

        while(current->getLeft() != nullptr){//While there is a left subtree in the right child
            current = current->getLeft();//Go the next left child
        }

    }else{//If there is no right subtree
			if(current->getParent() == nullptr){
				return nullptr;
			}
			while(current->getKey() > current->getParent()->getKey()){
					current = current->getParent();//Go to parent
					if(current->getParent() == nullptr){
						return nullptr;
					}
			}
			
			current = current->getParent();
    }

    return current;
}

/**
* A method to remove all contents of the tree and
* reset the values in the tree for use again.
*/
template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::clear()
{
    clearHelper(root_);
		root_ = nullptr;
}

template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::clearHelper(Node<Key, Value> *r){
    //Post-order traversal   
		if(r == nullptr){
			return;
		}
		
		clearHelper(r->getLeft());
		clearHelper(r->getRight()); 
		
		delete r;
		//r = nullptr;
    return;		
}


/**
* A helper function to find the smallest node in the tree.
*/
template<typename Key, typename Value>
Node<Key, Value>*
BinarySearchTree<Key, Value>::getSmallestNode() const
{

		//BC
		if(root_->getLeft() == nullptr){
			return root_;
		}

    //Left most item in entire tree
    Node<Key, Value> *smallest = root_;
    while(smallest != nullptr){
        if(smallest->getLeft() != nullptr){
        	smallest = smallest->getLeft();
				}else{
					break;
				}
    }
		//std::cout << "Smallest node is " << smallest->getKey() << std::endl;
    return smallest;
    
}

/**
* Helper function to find a node with given key, k and
* return a pointer to it or nullptr if no item with that key
* exists
*/
template<typename Key, typename Value>
Node<Key, Value>* BinarySearchTree<Key, Value>::internalFind(const Key& key) const
{
    Node<Key, Value>* temp = root_;
    while(temp != nullptr){
        if(temp->getKey() < key){
            temp = temp->getRight();
        }else if(temp->getKey() > key ){
            temp = temp->getLeft();
        }else{
            return temp;            
        }
    }
    return nullptr;
}

/**
 * Return true iff the BST is balanced.
 */
template<typename Key, typename Value>
int BinarySearchTree<Key, Value>::calculateHeightIfBalanced(Node<Key, Value>* root) const{
	// Base case: an empty tree is always balanced and has a height of 0
	if (root == nullptr) return 0;

	// TODO: handle the cases here
	if( !isBalancedHelper(root->getLeft()) || !isBalancedHelper(root->getRight())){
		return -1;//because parent is unbalanced
	}

	if( abs(calculateHeightIfBalanced(root->getLeft()) - calculateHeightIfBalanced(root->getRight())) > 1){
		return -1;
	}

	//If both subtrees are balanced, return the height of the longest one + 1
	return 1 + std::max(calculateHeightIfBalanced(root->getLeft()),calculateHeightIfBalanced(root->getRight()));
}

template<typename Key, typename Value>
bool BinarySearchTree<Key, Value>::isBalancedHelper(Node<Key, Value> *root) const{	
	//Determine if left tree and right tree are both balanced
	if(root == nullptr){
		return true;
	}

	int leftHeight = calculateHeightIfBalanced(root->getLeft());
	int rightHeight = calculateHeightIfBalanced(root->getRight());

	if(calculateHeightIfBalanced(root->getLeft()) == -1 || calculateHeightIfBalanced(root->getRight()) == -1){
		return false;
	}else if(abs(leftHeight-rightHeight) > 1 ){
		return false;
	}

	return true;
}

template<typename Key, typename Value>
bool BinarySearchTree<Key, Value>::isBalanced() const
{
  return isBalancedHelper(root_);
}



template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::nodeSwap( Node<Key,Value>* n1, Node<Key,Value>* n2)
{
    if((n1 == n2) || (n1 == nullptr) || (n2 == nullptr) ) {
        return;
    }
    Node<Key, Value>* n1p = n1->getParent();
    Node<Key, Value>* n1r = n1->getRight();
    Node<Key, Value>* n1lt = n1->getLeft();
    bool n1isLeft = false;
    if(n1p != nullptr && (n1 == n1p->getLeft())) n1isLeft = true;
    Node<Key, Value>* n2p = n2->getParent();
    Node<Key, Value>* n2r = n2->getRight();
    Node<Key, Value>* n2lt = n2->getLeft();
    bool n2isLeft = false;
    if(n2p != nullptr && (n2 == n2p->getLeft())) n2isLeft = true;


    Node<Key, Value>* temp;
    temp = n1->getParent();
    n1->setParent(n2->getParent());
    n2->setParent(temp);

    temp = n1->getLeft();
    n1->setLeft(n2->getLeft());
    n2->setLeft(temp);

    temp = n1->getRight();
    n1->setRight(n2->getRight());
    n2->setRight(temp);

    if( (n1r != nullptr && n1r == n2) ) {
        n2->setRight(n1);
        n1->setParent(n2);
    }
    else if( n2r != nullptr && n2r == n1) {
        n1->setRight(n2);
        n2->setParent(n1);

    }
    else if( n1lt != nullptr && n1lt == n2) {
        n2->setLeft(n1);
        n1->setParent(n2);

    }
    else if( n2lt != nullptr && n2lt == n1) {
        n1->setLeft(n2);
        n2->setParent(n1);

    }


    if(n1p != nullptr && n1p != n2) {
        if(n1isLeft) n1p->setLeft(n2);
        else n1p->setRight(n2);
    }
    if(n1r != nullptr && n1r != n2) {
        n1r->setParent(n2);
    }
    if(n1lt != nullptr && n1lt != n2) {
        n1lt->setParent(n2);
    }

    if(n2p != nullptr && n2p != n1) {
        if(n2isLeft) n2p->setLeft(n1);
        else n2p->setRight(n1);
    }
    if(n2r != nullptr && n2r != n1) {
        n2r->setParent(n1);
    }
    if(n2lt != nullptr && n2lt != n1) {
        n2lt->setParent(n1);
    }


    if(this->root_ == n1) {
        this->root_ = n2;
    }
    else if(this->root_ == n2) {
        this->root_ = n1;
    }

}

/**
 * Lastly, we are providing you with a print function,
   BinarySearchTree::printRoot().
   Just call it with a node to start printing at, e.g:
   this->printRoot(this->root_) // or any other node pointer

   It will print up to 5 levels of the tree rooted at the passed node,
   in ASCII graphics format.
   We hope it will make debugging easier!
  */

// include print function (in its own file because it's fairly long)
#include "print_bst.h"

/*
---------------------------------------------------
End implementations for the BinarySearchTree class.
---------------------------------------------------
*/

#endif