//
//  BST.h
//  BSThw
//
//  Created by Joshua Garza on 4/12/18.
//  Copyright © 2018 Joshua Garza. All rights reserved.
//

#ifndef BST_h
#define BST_h
#include <iostream>
#include <algorithm>
using namespace std;

class binarySearchTree
{
private:
    class node
    {
    public:
        node * left;
        node * right;
        double data;

        node(double x)
        {
            left = NULL;
            right = NULL;
            data = x;
        }

    };

    node * root;
    node * temp;
    node * current;
    node * doomedNode;
    node * trailCurrent;

    void recInsert(node * &r, double x)
    {
        if (r == NULL)
        {
            r = new node(x);
        }
        else
        {
            //check to see if x is less than root->data
            if (x < r->data)
            {
                recInsert(r->left, x);
            }
            else //check to see if x is greater than root->data
            {
                recInsert(r->right, x);
            }
        }
    }

    node * recRemove(node * root, double data)
    {
        //3 cases: no children, one child, 2 children
        if (root == NULL)
        {
            return NULL;
        }
        else if (data < root->data)
        {
            root->left = recRemove(root->left, data);
        }
        else if(data > root->data)
        {
            root->right = recRemove(root->right, data);
        }
        else
        {
            if (root->right == NULL && root->left == NULL) //no children
            {
                delete root;
                root = NULL;
                return root;
            }
            else if(root->left == NULL) //only right child
            {
                temp = root;
                root = root->right;
                delete temp;
                return root;
            }
            else if(root->right == NULL) //only left child
            {
                temp = root;
                root = root->left;
                delete temp;
                return root;
            }
            else //2 children
            {
                temp->data = findMin(root->right);
                root->data = temp->data;
                root->right = recRemove(root->right, temp->data);
            }
        }

        return root;
    }

    void displayInOrder(node * r) //display tree in oder
    {
        if(r == NULL)
        {
            //do nothing
        }
        else
        {
            displayInOrder(r->left);
            cout << r->data << endl;
            displayInOrder(r->right);
        }
    }

    void displayPreOrder(node * r)
    {
        if(r == NULL)
        {
            //do nothing
        }
        else
        {
            cout << r->data << endl;
            displayPreOrder(r->left);
            displayPreOrder(r->right);
        }
    }

    void displayPostOrder(node * r)
    {
        if(r == NULL)
        {
            //do nothing
        }
        else
        {
            displayPostOrder(r->left);
            displayPostOrder(r->right);
            cout << r->data << endl;
        }
    }
    //recursive function that returns the number of leaves(a node who has no children)
    int recNumLeaves(node * p)
    {
        if (p == NULL)
        {
            return 0;
        }
        if (p->left == NULL && p->right == NULL)
        {
            return 1;
        }
        else //recursive call
        {
            return recNumLeaves(p->left) + recNumLeaves(p->right);
        }
    }
    //recursive function that returns the number of nodes in the tree
    int recNumItems(node * p)
    {
        if (p == NULL)
        {
            return 0;
        }
        else
        {
            return 1 + recNumItems(p->left) + recNumItems(p->right);
        }
    }
    //recursive function that gets the height of the tree
    int recGetHeight(node * p)
    {
        if(p == NULL)
        {
            return -1;
        }
        else
        {
            int L = recGetHeight(p->left);
            int R = recGetHeight(p->right);
            return max(L,R) + 1;
        }
    }
    //found this function on geeksforgeeks.org
    int recFullNodes(node * root)
    {
        if (root == NULL)
        {
            return 0;
        }
        int count = 0;
        if(root->left && root->right)
        {
            count++;
        }
        count += (recFullNodes(root->left) + recFullNodes(root->right));
        return count;
    }

        double findMin(node * p)
        {
            if(p == NULL)
            {
                return -1;
            }
            else
            {
                //in a balanced BST the minimum node is the leftmost node so,
                //we traverse the left subtree until we get to the leftmost node and return and remove it.
                temp = p;
                while(temp->left != NULL)
                {
                    temp = temp->left;
                }
                return temp->data;
            }
        }

    double findMax(node * p)
    {
        if(p == NULL)
        {
            return -1;
        }
        else
        {
            //in a balanced BST the maximum node is the rightmost node so,
            //we traverse the right subtree until we get to the rightmost node and return and remove it.
            temp = p;
            while(temp->right != NULL)
            {
                temp = temp->right;
            }
            return temp->data;
        }
    }
    //I found this and the next function on geeksforgeeks.org
    void printGivenLevel(node * root, int level)
    {
        if (root == NULL)
        {
            return;
        }
        if (level == 1)
        {
            cout << root->data << " ";
        }
        else if (level > 1)
        {
            printGivenLevel(root->left, level-1);
            printGivenLevel(root->right, level-1);
        }
    }

    void printLevelOrder(node * root)
    {
        int h = recGetHeight(root);
        for(int i = 1; i <= h; i++)
        {
            printGivenLevel(root, i);
            cout << endl;
        }
    }
    node * sortedArrayBST(double * arr, int start, int end)
    {
        int mid = (start + end)/2;
        if (start > end)
        {
            return NULL;
        }
        //because the array will be sorted
        //the root of the tree will contain the item in the middle of the array so everything less than the middle will go in the left subtree
        //and everything greater than the middle will go in the right subtree
        root = new node(arr[mid]);
        //recursively make left subtree
        root->left = sortedArrayBST(arr, start, end-1);
        //recursively make left subtree
        root->right = sortedArrayBST(arr, mid + 1, end);

        return root;
    }


public:
    binarySearchTree()
    {
        root = NULL;
    }
    //constructor that builds a perfectly balanced BST when passed and array arr and number of items n
    binarySearchTree (double * arr, int start, int end)
    {
        root = sortedArrayBST(arr, start, end);
    }
    void insert(double x)
    {
        recInsert(root, x);
    }

    node * remove(double x) //not gonna work
    {
        return recRemove(root, x);
    }
        //method to remove smallest node
        node * extractMin()
        {
            return recRemove(root, findMin(root));
        }
    // method to remove largest node
    node * extractMax() // need to remove
    {
        // return findMax(root);
        return recRemove(root, findMax(root));
    }
    void displayInOrder()
    {
        displayInOrder(root);
    }
    void displayPreOrder()
    {
        displayPreOrder(root);
    }
    void displayPostOrder()
    {
        displayPostOrder(root);
    }
    //part 4: Implement a level order traversal.  State the worst-case big-oh run time of your method.
    //A "level order" visits the items in order of level, ie, root first, then roots children, then root's grandchildren, etc.
    void levelOrderDisplay()
    {
        printLevelOrder(root); //worst case run time: O(n^2)
    }
    //a leaf is a parent node whose left and right child are NULL;
   int numLeaves()
   {
       return recNumLeaves(root);
   }
    //returns total number of nodes
   int numItems()
   {
       return recNumItems(root);
   }
    //returns height of tree
   int getHeight()
   {
       return recGetHeight(root);
   }

    int fullNodes()
    {
        return recFullNodes(root);

    }


};

#endif /* BST_h */