examine what potantial problem with this implementation, particularly insert(), that cause infinite loop
#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