Below is first avlbst.h, which has some errors. and bst.h, which is completed. avlbst.h is built on bst.h. Find potential problems with avlbst.h, particularly with insert(), and the helper functions make may cause it to enter infinite loop
Beginning of avlbst.h
#ifndef RBBST_H
#define RBBST_H

#include <iostream>
#include <exception>
#include <cstdlib>
#include <algorithm>
#include "bst.h"

struct KeyError { };

/**
* A special kind of node for an AVL tree, which adds the height as a data member, plus
* other additional helper functions. You do NOT need to implement any functionality or
* add additional data members or helper functions.
*/
template <typename Key, typename Value>
class AVLNode : public Node<Key, Value>
{
public:
    // Constructor/destructor.
    AVLNode(const Key& key, const Value& value, AVLNode<Key, Value>* parent);
    virtual ~AVLNode();

    // Getter/setter for the node's height.
    int getHeight () const;
    void setHeight (int height);

    // Getters for parent, left, and right. These need to be redefined since they
    // return pointers to AVLNodes - not plain Nodes. See the Node class in bst.h
    // for more information.
    virtual AVLNode<Key, Value>* getParent() const override;
    virtual AVLNode<Key, Value>* getLeft() const override;
    virtual AVLNode<Key, Value>* getRight() const override;

protected:
    int height_;
};

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

/**
* An explicit constructor to initialize the elements by calling the base class constructor.
*/
template<class Key, class Value>
AVLNode<Key, Value>::AVLNode(const Key& key, const Value& value, AVLNode<Key, Value> *parent) :
    Node<Key, Value>(key, value, parent), height_(1)
{

}

/**
* A destructor which does nothing.
*/
template<class Key, class Value>
AVLNode<Key, Value>::~AVLNode()
{

}

/**
* A getter for the height of a AVLNode.
*/
template<class Key, class Value>
int AVLNode<Key, Value>::getHeight() const
{
    return height_;
}

/**
* A setter for the height of a AVLNode.
*/
template<class Key, class Value>
void AVLNode<Key, Value>::setHeight(int height)
{
    height_ = height;
}

/**
* An overridden function for getting the parent since a static_cast is necessary to make sure
* that our node is a AVLNode.
*/
template<class Key, class Value>
AVLNode<Key, Value> *AVLNode<Key, Value>::getParent() const
{
    return static_cast<AVLNode<Key, Value>*>(this->parent_);
}

/**
* Overridden for the same reasons as above.
*/
template<class Key, class Value>
AVLNode<Key, Value> *AVLNode<Key, Value>::getLeft() const
{
    return static_cast<AVLNode<Key, Value>*>(this->left_);
}

/**
* Overridden for the same reasons as above.
*/
template<class Key, class Value>
AVLNode<Key, Value> *AVLNode<Key, Value>::getRight() const
{
    return static_cast<AVLNode<Key, Value>*>(this->right_);
}


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


template <class Key, class Value>
class AVLTree : public BinarySearchTree<Key, Value>
{
public:
    virtual void insert (const std::pair<const Key, Value> &new_item); // TODO
    virtual void remove(const Key& key);  // TODO
protected:
    virtual void nodeSwap( AVLNode<Key,Value>* n1, AVLNode<Key,Value>* n2);

    // Add helper functions here
    void rotateLeft(AVLNode<Key, Value>* node);
    void rotateRight(AVLNode<Key, Value>* node);
    void updateHeight(AVLNode<Key, Value>* node);
    void rebalance(AVLNode<Key, Value>* node);
    int rebalanceHelper(AVLNode<Key, Value>* node);

};

template<class Key, class Value>
void AVLTree<Key, Value>::insert (const std::pair<const Key, Value> &new_item)
{
    //insert method similar to bst.h
    if (this->root_ == nullptr) { // Tree is empty, insert at root
        this->root_ = new AVLNode<Key, Value>(new_item.first, new_item.second, nullptr);
        return;
    }

    AVLNode<Key, Value>* existNode = static_cast<AVLNode<Key, Value>*>(this->internalFind(new_item.first));
    if (existNode != nullptr) { // If key exists, update value
        existNode->setValue(new_item.second);
        return;
    }

    AVLNode<Key, Value>* curr = static_cast<AVLNode<Key, Value>*>(this->root_); // Start from root
    AVLNode<Key, Value>* parent = nullptr;

    while (curr != nullptr) { // Traversing
        parent = curr;
        if (curr->getKey() > new_item.first) { // Go left
            if (curr->getLeft() == nullptr) { // if no leftchild, insert
                curr->setLeft(new AVLNode<Key, Value>(new_item.first, new_item.second, curr));
                break;
            }
            curr = curr->getLeft();
        } 
        else { // Go right
            if (curr->getRight() == nullptr) { // if no rightchild, insert
                curr->setRight(new AVLNode<Key, Value>(new_item.first, new_item.second, curr));
                break; 
            }
            curr = curr->getRight();
        }
    }

    //update height and rebalance (if needed)
    for (AVLNode<Key, Value>* node = parent; node != nullptr; node = node->getParent()) {
        updateHeight(node); 
        rebalance(node);    
    }
}

template<class Key, class Value>
void AVLTree<Key, Value>:: remove(const Key& key)
{
    //remove method similar to bst.h
    AVLNode<Key, Value>* todelete = static_cast<AVLNode<Key, Value>*>(this->internalFind(key));

    if (todelete == nullptr) {//not found
        return;
    }


    if (todelete->getLeft() != nullptr && todelete->getRight() != nullptr) {//two children
        AVLNode<Key, Value>* pred = static_cast<AVLNode<Key, Value>*>(this->predecessor(todelete));
        nodeSwap(todelete, pred);
    }

    // Now has at most one child
    AVLNode<Key, Value>* parent = todelete->getParent();
    AVLNode<Key, Value>* child = todelete->getLeft();
    if (todelete->getLeft() == nullptr) {
        child = todelete->getRight();
    }

    if (child != nullptr){//update parent for child
        child -> setParent(parent);
    }

    if (parent == nullptr) {//update parent for root
        this->root_ = child;
    } else if (todelete == parent->getLeft()) {
        parent->setLeft(child);
    } else {
        parent->setRight(child);
    }

    delete todelete; // Delete the todelete node

    //Update heights and rebalance upward
    for (AVLNode<Key, Value>* node = parent; node; node = node->getParent()) {
        updateHeight(node); 
        rebalance(node);    
    }
    
}

template<class Key, class Value>
void AVLTree<Key, Value>::nodeSwap( AVLNode<Key,Value>* n1, AVLNode<Key,Value>* n2)
{
    BinarySearchTree<Key, Value>::nodeSwap(n1, n2);
    int tempH = n1->getHeight();
    n1->setHeight(n2->getHeight());
    n2->setHeight(tempH);
}


//beginning of helper functions
template<class Key, class Value>
void AVLTree<Key, Value>::rotateLeft(AVLNode<Key, Value>* node)
{
    AVLNode<Key, Value>* pivot = node->getRight(); //right child becomes pivot
    AVLNode<Key, Value>* parent = node->getParent();


    if (pivot -> getLeft() != nullptr) {//pivot left child become node right child
        node->setRight(pivot->getLeft());
        pivot->getLeft()->setParent(node);
    }

    pivot->setParent(parent); //update parent for pivot
    if (parent == nullptr) { 
        this->root_ = pivot;
    } else if (node == parent->getLeft()) {
        parent->setLeft(pivot);
    } else {
        parent->setRight(pivot);
    }

    pivot->setLeft(node);//update for pivot and node
    node->setParent(pivot);

    updateHeight(node);//update height
    updateHeight(pivot);
}

template<class Key, class Value>
void AVLTree<Key, Value>::rotateRight(AVLNode<Key, Value>* node)
{
    AVLNode<Key, Value>* pivot = node->getLeft(); // Left child becomes the pivot
    AVLNode<Key, Value>* parent = node->getParent(); 

    node->setLeft(pivot->getRight()); // pivot right child becomes node left child
    if (pivot->getRight()) {
        pivot->getRight()->setParent(node);
    }

    pivot->setParent(parent); // update parent for pivot
    if (!parent) {
        this->root_ = pivot; 
    } else if (node == parent->getLeft()) {
        parent->setLeft(pivot);
    } else {
        parent->setRight(pivot);
    }

    pivot->setRight(node); // update for pivot and node
    node->setParent(pivot);

    // Update heights of the rotated nodes
    updateHeight(node);
    updateHeight(pivot);
}


template<class Key, class Value>
void AVLTree<Key, Value>::updateHeight(AVLNode<Key, Value>* node)
{
    if (node == nullptr) {//check if node exist
        return;
    }

    int leftHeight = 0;
    int rightHeight = 0;

    if (node -> getLeft() != nullptr){//get left height
        leftHeight = node -> getLeft() -> getHeight();
    }
    if (node -> getRight() != nullptr){//get right height
        rightHeight = node -> getRight() -> getHeight();
    }

    node -> setHeight(1 + std::max(leftHeight, rightHeight));//update
}


template<class Key, class Value>
int AVLTree<Key, Value>::rebalanceHelper(AVLNode<Key, Value>* node)
{
    if (node == nullptr) {
        return 0;
    }

    int leftHeight = 0;
    int rightHeight = 0;

    if (node -> getLeft() != nullptr){//get left height
        leftHeight = node -> getLeft() -> getHeight();
    }
    if (node -> getRight() != nullptr){//get right height
        rightHeight = node -> getRight() -> getHeight();
    }

    return leftHeight - rightHeight; //difference
}



template<class Key, class Value>
void AVLTree<Key, Value>::rebalance(AVLNode<Key, Value>* node)
{
    if (node == nullptr) {
        return;
    }
   int balance = rebalanceHelper(node); //get left/right difference

    if (balance > 1) {//tilted left
        if (rebalanceHelper(node->getLeft()) < 0) {//zig zag case: left then right
            rotateLeft(node->getLeft());
        }
        rotateRight(node);
    }

    else if (balance < -1) {//titled right
        if (rebalanceHelper(node->getRight()) > 0) {//zig zag case: right then left
            rotateRight(node->getRight());
        }
        rotateLeft(node);
    }
}



#endif

Beginning of bst.h
#ifndef BST_H
#define BST_H

#include <iostream>
#include <exception>
#include <cstdlib>
#include <utility>
#include <algorithm>
/**
 * 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_(NULL),
    right_(NULL)
{

}

/**
* 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 within the deleteAll() helper method in 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
{
    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;
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=(const iterator& rhs);    
        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;


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
    int getHeight(Node<Key, Value>* node) const;
    bool isBalancedHelper(Node<Key, Value>* node) const;
    void clearAll(Node<Key, Value>* node);

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)
{
    //Todo
    current_ = ptr;
    
}

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

/**
* 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
{
    // TODO
    return this -> 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
{
    // TODO
    return this -> current_ != rhs.current_;

}

// template<class Key, class Value>
// typename BinarySearchTree<Key, Value>::iterator&
// BinarySearchTree<Key, Value>::iterator::operator=(const BinarySearchTree<Key, Value>::iterator& rhs)
// {
//     this->current_ = rhs.current_;
//     return *this;
// }

/**
* 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++()
{
    // TODO
    if (current_ == nullptr){//check if current node exists
        return *this; 
    }

    if (current_ -> getRight() != nullptr){//if right child exists, move right once then all left
        current_ = current_ -> getRight();
        while (current_ -> getLeft() != nullptr){
            current_ = current_ -> getLeft();
        }
    }

    else if (current_ -> getRight() == nullptr){// no right child, move up until the 1st left child
       Node<Key, Value>* parent = current_ -> getParent();
       while (parent != nullptr && current_ == parent -> getRight()){
               current_ = parent;
               parent = parent -> getParent();  
       }
       current_ = parent;
    }
    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 NULL.
*/
template<class Key, class Value>
BinarySearchTree<Key, Value>::BinarySearchTree() : root_(nullptr)
{   
    // TODO

}

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

}

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

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(NULL);
    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;
}


/**
* An insert method to insert into a Binary Search Tree.
* The tree will not remain balanced when inserting.
*/
template<class Key, class Value>
void BinarySearchTree<Key, Value>::insert(const std::pair<const Key, Value> &keyValuePair)
{
    if (root_ == nullptr){ // if tree is empty, insert at root
        root_ = new Node<Key, Value>(keyValuePair.first, keyValuePair.second, nullptr);
        return;
    }

    Node<Key, Value>* existNode = internalFind(keyValuePair.first);
    if (existNode != nullptr){ // if key exists, update value
        existNode -> setValue(keyValuePair.second);
        return;
    }
  
    Node<Key, Value>* curr = root_;// start from root
    while (curr != nullptr){//traversing
        if (curr -> getKey() > keyValuePair.first){ // go left
            if (curr -> getLeft() == nullptr){// if no left child, insert
                curr -> setLeft(new Node<Key, Value>(keyValuePair.first, keyValuePair.second, curr));
                return;
            }         
            curr = curr -> getLeft();
        } 
        else{ // go right
            if (curr -> getRight() == nullptr){// if no right child, insert
                curr -> setRight(new Node<Key, Value>(keyValuePair.first, keyValuePair.second, curr));
                return;
            }
            curr = curr -> getRight();
        }
    }
}


/**
* A remove method to remove a specific key from a Binary Search Tree.
* The tree may not remain balanced after removal.
*/
template<typename Key, typename Value>
void BinarySearchTree<Key, Value>::remove(const Key& key)
{
    // TODO
    Node<Key, Value>* todelete = internalFind(key);
    if (todelete == nullptr){ //do nothing
        return;
    }

    if (todelete -> getLeft() != nullptr && todelete -> getRight() != nullptr){ // 2 children
        Node<Key, Value>* pred = predecessor(todelete);
        nodeSwap(todelete, pred);
    }

    Node<Key, Value>* child = todelete -> getLeft(); //now at most only 1 child
    Node<Key, Value>* parent = todelete -> getParent();
    if (todelete -> getLeft() == nullptr){
        child = todelete -> getRight();
    }
    
    //update parent for child
    if (child != nullptr){
        child -> setParent(parent);
    }

    //update parent for root
    if (parent == nullptr){
        root_ = child;
    }
    else if (todelete == parent -> getLeft()){//update child
        parent -> setLeft(child);
    }
    else{//update child
        parent -> setRight(child);
    }

    delete todelete;
}



template<class Key, class Value>
Node<Key, Value>*
BinarySearchTree<Key, Value>::predecessor(Node<Key, Value>* current)
{
    // TODO
    if (current == nullptr){
        return nullptr;
    }

    if (current -> getLeft() != nullptr){ //go left once then all right
        current = current -> getLeft(); 
        while (current -> getRight() != nullptr){
            current = current -> getRight();
        }
        return current;
    }

    //otherwise check parents
    Node<Key, Value>* parent = current -> getParent();
    while (parent != nullptr && current == parent -> getLeft()){
           current = parent;
           parent = parent -> getParent();
    }

    return parent;
}

template<class Key, class Value>
void BinarySearchTree<Key, Value>::clearAll(Node<Key, Value>* node){
    if (node == nullptr){
        return;
    }

    clearAll(node -> getLeft());
    clearAll(node -> getRight());
    delete node;
}

/**
* 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()
{
    clearAll(root_);
    root_ = nullptr;
}


/**
* A helper function to find the smallest node in the tree.
*/
template<typename Key, typename Value>
Node<Key, Value>*
BinarySearchTree<Key, Value>::getSmallestNode() const
{
    // TODO
    Node<Key, Value>* curr = root_;
    if (curr == nullptr){
        return nullptr;
    }

    while (curr -> getLeft() != nullptr){//go left until no left child
        curr = curr -> getLeft();
    }
    return curr;
}

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

        else if (curr -> getKey() > key){//go left
        curr = curr -> getLeft();
        }

        else{//go right
        curr = curr -> getRight();
        }
    }
    return nullptr; //not found
}


template<typename Key, typename Value>
int BinarySearchTree<Key, Value>::getHeight(Node<Key, Value>* node) const //added helper func to get height
{
    if (node == nullptr){
        return 0;
    }

    return 1 + std::max(getHeight(node -> getLeft()), getHeight(node -> getRight()));
}

template<typename Key, typename Value>
bool BinarySearchTree<Key, Value>::isBalancedHelper(Node<Key, Value>* node) const //added helper func for isBalanced
{
    if (node == nullptr){
        return true;
    }

    int left = getHeight(node -> getLeft());
    int right = getHeight(node -> getRight());

    if (std::abs(left - right) > 1){// height diff > 1
        return false;
    }

    return isBalancedHelper(node -> getLeft()) && isBalancedHelper(node -> getRight());
}

/**
 * Return true iff the BST is balanced.
 */
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 == NULL) || (n2 == NULL) ) {
        return;
    }
    Node<Key, Value>* n1p = n1->getParent();
    Node<Key, Value>* n1r = n1->getRight();
    Node<Key, Value>* n1lt = n1->getLeft();
    bool n1isLeft = false;
    if(n1p != NULL && (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 != NULL && (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 != NULL && n1r == n2) ) {
        n2->setRight(n1);
        n1->setParent(n2);
    }
    else if( n2r != NULL && n2r == n1) {
        n1->setRight(n2);
        n2->setParent(n1);

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

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

    }


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

    if(n2p != NULL && n2p != n1) {
        if(n2isLeft) n2p->setLeft(n1);
        else n2p->setRight(n1);
    }
    if(n2r != NULL && n2r != n1) {
        n2r->setParent(n1);
    }
    if(n2lt != NULL && 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