Binary Search Tree C++ Cheat Sheet by BearTeddy

template <class T>
class TreeNode {
private:
    T _item;
    TreeNode<T>* _left;
    TreeNode<T>* _right;
    //Could include
    TreeNode<T>* _parent;
    int _height;
public:
    TreeNode(T x) {
     _left = _right = NULL;
     _item = x;
     _height = 0; };
     friend BinarySearchTree<T>;
};

template <class T>
T BinarySearchTree<T>::searchMax() {
     TreeNode<T>* current = _root;
     while (current->_right) {
           current = current->_right;
      }
      return current->_item;
}

template <class T>
T BinarySearchTree<T>::searchMin() {
      TreeNode<T>* current = _root;
      while (current->_left) {
      current = current->_left;
      }
      return current->_item;
}

template <class T>
T BinarySearchTree<T>::successor(T x){
     TreeNode<T>* root = _root;
     T succ = NULL;
     while (root != NULL) {
       if (x < root->_item){
           succ = root->_item;
           root = root->_left;
        }
        else{
           root = root->_right;
        }
    }
    return succ;
}

//Iterative
template <class T>
bool BinarySearchTree<T>::exist(T x) {
        TreeNode<T>* nd = _root;
        while (nd != NULL) {
                if (nd->_item == x) return true;
                if (nd->_item > x) nd = nd->_left;
                else nd = nd->_right;
        }
        return false;
}

template <class T>
bool BinarySearchTree<T>::exist(TreeNode<T> Node,T x) {
         // RECURSIVE
         exists ( _root , value x )
         if (_root == null) return false;
         if (_root->_item == x) return true;
         if (_root->_item > x)
            return exists ( _root->left, x);
         else exists ( _root->right, x );
}

//LR Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_leftrightRotation(TreeNode<T> node)
{
node->_left = _rightRotation(node->_left);
node = _leftRotation(node);
return node;
}

//RL Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_rightleftRotation(TreeNode<T> node) {
node->_right = _leftRotation(node->_right);
node = _rightRotation(node);
return node;
}

template <class T>
void BinarySearchTree<T>::_preOrderPrint(TreeNode<T>* node) {
      if (!node) return;
      cout << node->_item << " ";
      _preOrderPrint(node->_left);
      _preOrderPrint(node->_right);
}

template <class T>
void BinarySearchTree<T> :: _inOrderPrint(TreeNode<T>* node) {
      if (!node) return;
      _inOrderPrint(node->_left);
      cout << node->_item << " ";
      _inOrderPrint(node->_right);
}

template <class T>
void BinarySearchTree<T>:: _postOrderPrint(TreeNode<T>* node) {
     if (!node) return;
     _postOrderPrint(node->_left);
     _postOrderPrint(node->_right);
     cout << node->_item << " ";
}

template <class T>
int BinarySearchTree<T>::height(TreeNode<T>* node) {
return node == NULL ? -1 : (node->_height);
}

template <class T>
int BinarySearchTree<T>::_calheight(TreeNode<T>* node) {
   int leftHeight = -1;
   int rightHeight = -1;
   if (node != NULL) {
     if (node->_left != NULL) {
        leftHeight = _calheight(node->_left);
     }
     if (node->_right != NULL) {
      rightHeight = _calheight(node->_right);
     }
   }
   return max(leftHeight, rightHeight) + 1;
}

//Height from TA
template <class T>
void TreeNode<T>::rectifyHeight()
{
 int left = _left ? _left->_height : -1;
 int right = _right ? _right->_height : -1;
//Height Value
 _height = (left > right ? left : right) + 1;
}

//Task 1 and 6
template <class T>
TreeNode<T> BinarySearchTree<T>::_insert(TreeNode<T> current, T x) {
    if (current->_item > x) {
      if (current->_left)
        current->_left = _insert(current->_left, x);
      else {
        current->_left = new TreeNode<T>(x);
        _size++;
       }
     }
    else if (x > current->_item) {
      if (current->_right)
         current->_right = _insert(current->_right, x);
      else{
         current->_right = new TreeNode<T>(x);
         _size++;
       }
     }
     else
//item already exists, dont need do anything
      return current;

//-1 if no children, st bf will work
int left = current->_left ? current->_left->_height : -1;

int right = current->_right ? current->_right->_height : -1;

current->_height = (left > right ? left : right) + 1;
    
  //GET DIFF IN height
  if (abs(left - right) > 1){
     
if (left > right){

       int LLH = current->_left->_left ? current->_left->_left->_height : 0;
       
       int LRH = current->_left->_right ? current->_left->_right->_height : 0;

    if (LLH < LRH){
    current->_left = _leftRotation(current->_left);
    }
    current = _rightRotation(current);

}
else {
    int RLH = current->_right->_left ? current->_right->_left->_height : 0;

    int RRH = current->_right->_right ? current->_right->_right->_height : 0;

    if (RRH < RLH){
    current->_right = _rightRotation(current->_right);
    }
    current = _leftRotation(current);

 }

}

//go through tree and rect height

   current->rectifyHeight();
   return current;

}

//LL Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_leftRotation(TreeNode<T> node)
{
TreeNode<T>* nd;
nd = node->_left;
node->_left = nd->_right;
nd->_right = node;

nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;


/*
*
*Codes from tutorialshorizon
*copyrights to - https://algorithms.tutorialhorizon.com/avl-tree-insertion/
*
//*/
//TreeNode<T>* nd = node->_right;
//TreeNode<T>* T2 = nd->_left;
//nd->_left = node;
//node->_right = T2;
//nd->_height = calheight(nd);
//node->_height = calheight(node);
//return nd;
}

//RR Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_rightRotation(TreeNode<T> node)
{

TreeNode<T>* nd;
nd = node->_right;
node->_right = nd->_left;
nd->_left = node;
nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;

/*
*
*Codes from tutorialshorizon
*copyrights to - https://algorithms.tutorialhorizon.com/avl-tree-insertion/
*
*
//
TreeNode<T>* nd = node->_left;
TreeNode<T>* T2 = nd->_right;
nd->_right = node;
node->_left = T2;
nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;*/
}