#include <iostream>

#include <queue>

using namespace std;

template <typename T>

struct node

};

template <typename T>

class BST

};

template <typename T>

int BST<T>::get_height(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return -1;

}

return (max(get_height(root_ptr->left), get_height(root_ptr->right)) + 1);

}

template <typename T>

BST<T>::BST()

{

this->len = 0;

this->root = NULL;

}

template <typename T>

node<T> *BST<T>::get_new_node(const T &data)

{

node<T> *new_node = new node<T>;

new_node->data = data;

new_node->left = NULL;

new_node->right = NULL;

return new_node;

}

template <typename T>

BST<T>::~BST()

{

this->len = 0;

remove_all(this->root);

this->root = NULL;

}

template <typename T>

int BST<T>::get_length()

{

return this->len; // Get the length of the BST

}

template <typename T>

node<T> *BST<T>::get_root()

{

return this->root; // Get the root of the BST

}

template <typename T> // Duplicates are not allowed

node<T> *BST<T>::insert(node<T> *root_ptr, const T &data)

{

if (root_ptr == NULL)

{

return get_new_node(data);

}

else if (data < root_ptr->data)

{

root_ptr->left = insert(root_ptr->left, data);

}

else if (data > root_ptr->data)

{

root_ptr->right = insert(root_ptr->right, data);

}

return root_ptr;

}

template <typename T>

void BST<T>::add(const T &data)

{

this->len++;

this->root = insert(this->root, data);

}

template <typename T>

node<T> *BST<T>::search(node<T> *root_ptr, const T &data)

{

if (root_ptr == NULL)

{

return NULL;

}

else if (root_ptr->data == data)

{

return root_ptr;

}

else if (root_ptr->data < data)

{

search(root_ptr->right, data);

}

else

{

search(root_ptr->left, data);

}

}

template <typename T>

node<T> *BST<T>::find(const T &data)

{

return search(this->root, data);

}

template <typename T>

void BST<T>::print_preorder(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return;

}

else

{

cout << root_ptr->data << ' ';

print_preorder(root_ptr->left);

print_preorder(root_ptr->right);

}

}

template <typename T>

void BST<T>::print_inorder(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return;

}

else

{

print_inorder(root_ptr->left);

cout << root_ptr->data << ' ';

print_inorder(root_ptr->right);

}

}

template <typename T>

void BST<T>::print_levelorder(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return;

}

else

{

queue<node<T> *> node_queue;

node_queue.push(root_ptr);

while (!node_queue.empty())

{

node<T> *current_node = node_queue.front();

cout << current_node->data << ' ';

node_queue.pop();

if (current_node->left)

{

node_queue.push(current_node->left);

}

if (current_node->right)

{

node_queue.push(current_node->right);

}

}

}

}

template <typename T>

void BST<T>::print_postorder(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return;

}

else

{

print_postorder(root_ptr->left);

print_postorder(root_ptr->right);

cout << root_ptr->data << ' ';

}

}

template <typename T>

node<T> *BST<T>::find_min(node<T> *root_ptr)

{

while (root_ptr->left != NULL)

{

root_ptr = root_ptr->left;

}

return root_ptr;

}

template <typename T>

node<T> *BST<T>::find_max(node<T> *root_ptr)

{

while (root_ptr->right != NULL)

{

root_ptr = root_ptr->right;

}

return root_ptr;

}

template <typename T>

void BST<T>::remove_all(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return;

}

remove_all(root_ptr->left);

remove_all(root_ptr->right);

delete root_ptr;

}

template <typename T>

node<T> *BST<T>::inorder_successor(node<T> *root_ptr)

{

if (root_ptr == NULL)

{

return NULL;

}

// Now if the node has a right subtree return the minimum of that subtree

if (root_ptr->right != NULL)

{

return find_min(root_ptr->right);

}

else

{

// Traverse the tree from the root node until that value is found (value=>node of which successor is to be found)

node<T> *successor = NULL;

node<T> *ancestor = this->root;

while (ancestor != root_ptr)

{

if (root_ptr->data < ancestor->data)

{

successor = ancestor;

ancestor = ancestor->left;

}

else

{

ancestor = ancestor->right;

}

}

return successor;

}

}

template <typename T>

node<T> *BST<T>::delete_node(node<T> *root_ptr, const T &data)

{

if (root_ptr == NULL)

{

return root_ptr;

}

else if (data < root_ptr->data)

{

root_ptr->left = delete_node(root_ptr->left, data);

}

else if (data > root_ptr->data)

{

root_ptr->right = delete_node(root_ptr->right, data);

}

else

{

// Node to be deleted has been found here

// Case 1: No Child

if (root_ptr->left == NULL && root_ptr->right == NULL)

{

delete root_ptr;

}

else if (root_ptr->left == NULL)

{ // Case 2: One Child

node<T> *temp = root_ptr;

root_ptr = root_ptr->right;

delete temp;

}

else if (root_ptr->right == NULL)

{

node<T> *temp = root_ptr;

root_ptr = root_ptr->left;

delete temp;

}

else

{

// Case 3: With both the children

node<T> *temp = find_min(root_ptr->right); // We could also find the maximum of the left subtree

root_ptr->data = temp->data;

root_ptr->right = delete_node(root_ptr->right, temp->data);

}

}

return root_ptr;

}

template <typename T>

void BST<T>::remove(const T &data)

{

this->root = delete_node(this->root, data);

this->len--;

return;

}