// -------------------------------------------------------------
// Algoritmos e Estruturas de Dados 2024/2025 - LEIC (FCUP/FEUP)
// http://www.dcc.fc.up.pt/~pribeiro/aulas/aed2425/
// -------------------------------------------------------------
// Binary Search Tree
// Last update: 16/11/2024
// -------------------------------------------------------------

#ifndef BSTREE_H
#define BSTREE_H

#include <iostream>

template <class T> class BSTree {
private:
  struct Node {
    T value;            // The value stored on the node
    Node *left, *right; // Pointers to left and right child
  };
  
  Node *root;
  
public:

  // Constructor: initially the tree is empty
  BSTree() {
    root = nullptr;
  }

  // Destructor: delete all nodes (garbage collection)
  ~BSTree() {
    destroy(root);
  }

  // Recursively delete left and right subtrees and then current node
  void destroy(Node *n) {
    if (n == nullptr) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
  }

  // ---------------------------------------------------------
  // Count the number of nodes
  // ---------------------------------------------------------
  
  int numberNodes() {
    return numberNodes(root);
  }   
  
  int numberNodes(Node *n) {
    if (n == nullptr) return 0;
    return 1 + numberNodes(n->left) + numberNodes(n->right);
  }

  // ---------------------------------------------------------
  // Height of the tree
  // ---------------------------------------------------------

  int height() {
    return height(root);
  }
  
  int height(Node *n) {
    if (n == nullptr) return -1;
    return 1 + std::max(height(n->left), height(n->right));
  }

  // ---------------------------------------------------------
  // Does the tree contain value 'val' ?
  // ---------------------------------------------------------

  bool contains(const T & val) {
    return contains(root, val);
  }

  bool contains(Node *n, const T & val) {
    if (n == nullptr) return false;
    if (val < n->value) return contains(n->left, val);
    if (val > n->value) return contains(n->right, val);
    return true;
  }

  // ---------------------------------------------------------
  // Insert value 'val' in the tree
  // ---------------------------------------------------------
  
  bool insert(const T & val) {
    if (contains(val)) return false;
    root = insert(root, val);
    return true;
  }

  Node *insert(Node *n, const T & val) {
    if (n == nullptr) {
      Node *aux = new Node;
      aux->value = val;
      aux->left = aux->right = nullptr;
      return aux;
    } else if (val < n->value) {
      n->left = insert(n->left, val);
    } else if (val > n->value) {
      n->right = insert(n->right, val);
    }
    return n;
  }

  // ---------------------------------------------------------
  // Remove value 'val' from the tree
  // ---------------------------------------------------------

  bool remove(const T & val) {
    if (!contains(val)) return false;
    root = remove(root, val);
    return true;
  }

  Node *remove(Node *n, const T & val) {
    if (val < n->value) n->left = remove(n->left, val);
    if (val > n->value) n->right = remove(n->right, val);
    else if (n->left == nullptr) {
      Node *tmp = n->right;
      delete n;
      return tmp;
    } else if (n->right == nullptr) {
      Node *tmp = n->left;
      delete n;
      return tmp;
    } else {
      Node *max = n->left;
      while (max->right != nullptr) max = max->right;
      n->value = max->value;
      n->left = remove(n->left, max->value);
    }
    return n;
  }
  
  // ---------------------------------------------------------
  // Print tree in preorder, incluing N for the null values
  // ---------------------------------------------------------  
  
  void printPreOrder() {
    std::cout << "preOrder:";
    printPreOrder(root);
    std::cout << std::endl;
  }

  void printPreOrder(Node *n) {
    if (n == nullptr)
      std::cout << " N";
    else {
      std::cout << " " << n->value;
      printPreOrder(n->left);
      printPreOrder(n->right);
    }
  }
  
  // ---------------------------------------------------------
  // TODO: put the functions you need to implement below this
  // ---------------------------------------------------------
  

  
};



#endif