/**
  * Autor: Victor Carbune
  * Echipa SD, 2012
  *
  * Modificari: Adrian Bogatu
  * Echipa SD, 2013
  *
  * Modificari: Cosmin Petrisor
  * Echipa SD, 2015
  *
  * Modificari: Cristian Creteanu
  * Echipa SD, 2017
  *
  * Modificari: Ioana Stefan
  * Echipa SD, 2018
  * License: LGPL
  */

#ifndef __BINARY_SEARCH_TREE__H
#define __BINARY_SEARCH_TREE__H

#include <iostream>

template <typename T>
class BinarySearchTree
{
public:
    BinarySearchTree() {
        pData = nullptr;
        leftNode = nullptr;
        rightNode = nullptr;
        parent = nullptr;
    }
    ~BinarySearchTree() {
        if (rightNode != nullptr) {
          delete rightNode;
        }

        if (leftNode != nullptr) {
          delete leftNode;
        }

        if (pData != nullptr) {
          delete pData;
        }
    }

    bool isEmpty() {
        return (pData == nullptr);
    }

    void insertKey(T x) {
        if(pData == nullptr) {
          pData = new T;
          *pData = x;
        } else {
          if (leftNode == nullptr && x < *pData) {
            leftNode =  new BinarySearchTree<T>;
            leftNode->pData = new T;
            *(leftNode->pData) = x;
            leftNode->leftNode = leftNode->rightNode = nullptr;
            leftNode->parent = this;
          } else if (x < *pData) {
            leftNode->insertKey(x);
          } else if (rightNode == nullptr && x >= *pData) {
            rightNode = new BinarySearchTree<T>;
            rightNode->pData = new T;
            *(rightNode->pData) = x;
            rightNode->leftNode = rightNode->rightNode = nullptr;
            rightNode->parent = this;
          } else if (x >= *pData) {
            rightNode->insertKey(x);
          }

        }
    }

    BinarySearchTree<T>* searchKey(T x) {

      if (pData == nullptr) {
          return nullptr;
        } else if (*pData == x) {
          return this;
        }
        if (x < *pData) {
          if (leftNode != nullptr) {
            return leftNode->searchKey(x);
          } else {
            return nullptr;
          }
        } else if ( x > *pData) {
          if (rightNode != nullptr) {
            return rightNode->searchKey(x);
          } else {
            return nullptr;
          }
        }

        return nullptr;
    }

    std::vector<T> inOrderDisplay() {
        std::vector<T> res;
        std::vector<T> v;
        if(pData == nullptr) {
          return res;
        }
        if (leftNode != nullptr) {
          v = leftNode->inOrderDisplay();
          for ( int i : v) {
            res.push_back(i);
          }
        }
        res.push_back(*pData);
        if (rightNode != nullptr) {
      v = rightNode->inOrderDisplay();
          for (int i : v) {
            res.push_back(i);
          }
        }

        return res;

    }

    T findMin() {
        // TODO 2
        return T();
    }

    T findMax() {
        // TODO 2
        return T();
    }

    int findLevels() {
        // TODO 3
        return 0;
    }

    std::vector<T> displayLevel(int level) {
        // TODO 3
        std::vector<T> res;
        return res;
    }

    int removex() {
      BinarySearchTree<T>* p;
      if (leftNode == NULL && rightNode == NULL) {
        if (parent == NULL) {
          delete this;
          return 1;
        } else {
          if (parent->leftNode == this) {
            parent->leftNode = NULL;
          } else {
            parent->rightNode = NULL;
          }
          delete this;
          return 0;
        }
      } else {
        if (leftNode != NULL) {
          p =leftNode;
          while(p->rightNode) {
            p = p->rightNode;
          }
        } else {
          p = rightNode;
          while(p->leftNode) {
            p = p->leftNode;
          }
        }
        *pData = *(p->pData);
        return p->removex();
      }

    }
    BinarySearchTree<T>* removeKey(T x) {
      BinarySearchTree<T>* node = searchKey(x);
      if (node != NULL) {
      node->removex();
    }
      return this;
    }
private:
    BinarySearchTree<T> *leftNode;
    BinarySearchTree<T> *rightNode;
    BinarySearchTree<T> *parent;
    T *pData;
};

#endif // __BINARY_SEARCH_TREE_H