using BinarySearchTree3102;

/*
 * Binary Search Tree for CSC 3102 Portfolio
*/

/*
 * --REQUIRED METHODS--
 * BinaryTree()
 * void Add(int val)
 * int? Remove(int val)
 * bool Has(int val)
 * int Height()
 * --OPTIONAL METHODS--
 * BTreeAdd(BTreeNode curr, int val)
 * BTreeRemove(BTreeNode curr, int val)
 * FindHeight(BTreeNode curr)
 * ToString() (instead I made a PrintTree() function)
 * 
 * --Methods that I implemented--
 * BtreeNode ReplacementNode(int value)
 * Print(BtreeNode node)
*/



namespace BinarySearchTree3102
{
    public class BtreeNode
    {
        public int data;
        public BtreeNode? RightChld, LeftChld, parent;

        BtreeNode()
        {
            data = 0;
            RightChld = null;
            LeftChld = null;
            parent = null;
        }

        public BtreeNode(int val)
        {
            data = val;
            RightChld = null;
            LeftChld = null;
            parent = null;
        }
    }

    public class BinaryTree
    {
        public BtreeNode? root;

        //default constructor
        public BinaryTree()
        {
            root = null;
        }

        public void Add(int val)
        {
            if (root == null)
            {
                root = new BtreeNode(val);
            }
            else
            {
                var node = root;
                while (true)
                {
                    if (val <= node.data) //move to the left 
                    {
                        if (node.LeftChld == null)
                        {
                            node.LeftChld = new BtreeNode(val);
                            node.LeftChld.parent = node;
                            break;
                        }
                        else
                        {
                            node = node.LeftChld;
                        }
                    }
                    else //move to the right
                    {
                        if (node.RightChld == null)
                        {
                            node.RightChld = new BtreeNode(val);
                            node.RightChld.parent = node;
                            break;
                        }
                        else
                        {
                            node = node.RightChld;
                        }
                    }
                } //end of while loop
            }
        }


        /*
         * removes the node that has the specified value
         * Uses Parent(int value) to find the parent of the node that is being removed
         * Uses ReplacementNode(int value) to figure out which node the parent will now point to
         * @value - the data of the node that is being removed
        */
        public int? Remove(int value)
        {
            if (value == root.data)
            {
                root = ReplacementNode(value);
                return value;
            }
            else
            {
                var node = ReplacementNode(value);
                return value;
            }
        }


        /*
         * checks to see if a value is stored in the Binary Search Tree
         * @val - the value you are checking to see if it is in the BST
        */
        public bool Has(int val)
        {
            var node = root;
            while (true)
            {
                if (node == null)
                {
                    return false;
                }
                else if (node.data == val)
                {
                    return true;
                }
                else if (val < node.data)
                {
                    node = node.LeftChld;
                }
                else //(node.data > val)
                {
                    node = node.RightChld;
                }
            }
        }


        //Height function that gets called
        public int Height()
        {
            if (root == null)
            {
                return 0;
            }
            else
            {
                return Height(root);
            }

        }

        //Height function that actually does the work
        private int Height(BtreeNode? node)
        {
            if (node == null)
            {
                return 0;
            }
            else
            {
                return Math.Max(1 + Height(node.LeftChld), 1 + Height(node.RightChld));
            }
        }

        /*
         * this returns the replacement node for the remove function
         * Replacement strategy is to go right first, then take the leftmost leafnode of the node that is being removed
         * @value - the value of the node that is being removed
        */
        private BtreeNode? ReplacementNode(int value)
        {
            var node = root;
            while (node != null)
            {
                if (node.data == value)
                {
                    break;
                }
                else if (value < node.data)
                {
                    node = node.LeftChld;
                }
                else
                {
                    node = node.RightChld;
                }
            }
            if (node == null)
            {
                return null;
            }

            BtreeNode? replacement;
            if (node.RightChld != null && node.LeftChld != null)
            {
                replacement = node.RightChld;
                while (replacement.LeftChld != null)
                {
                    replacement = replacement.LeftChld;
                }
                if (node.RightChld == replacement) //right child of the node we wanted to remove did not have any left children
                {
                    replacement.LeftChld = node.LeftChld;
                    replacement.LeftChld.parent = replacement;
                    replacement.parent = node.parent;
                }
                else //replacement is now the right-first, leftmost node
                {
                    if (replacement.RightChld != null)
                    {
                        replacement.RightChld.parent = replacement.parent;
                        replacement.parent.LeftChld = replacement.RightChld;
                    }
                    else //replacement.rChild == null
                    {
                        replacement.parent.LeftChld = null;
                    }
                    replacement.parent = node.parent;
                    replacement.LeftChld = node.LeftChld;
                    replacement.LeftChld.parent = replacement;
                    replacement.RightChld = node.RightChld;
                    replacement.RightChld.parent = replacement; //now make replacement's parent's r/l child = replacement
                }
            }
            else if (node.RightChld == null && node.LeftChld != null)
            {
                replacement = node.LeftChld;
                replacement.parent = node.parent;
                replacement.parent.LeftChld = replacement;
            }
            else if (node.RightChld != null && node.LeftChld == null)
            {
                replacement = node.RightChld;

                replacement.parent = node.parent; //now connect the parent to replacement
                replacement.parent.RightChld = replacement;

            }
            else //node.lChild == null && node.rChild == null
            {
                if (node.parent.LeftChld == node)
                {
                    node.parent.LeftChld = null;
                }
                else //node.parent.rChild == node
                {
                    node.parent.RightChld = null;
                }
                return null;
            }
            if (node == root)
            {

            }
            else if (node.parent.LeftChld == node)
            {
                replacement.parent.LeftChld = replacement;
            }
            else //node.parent.rChild == node
            {
                replacement.parent.RightChld = replacement;
            }
            return replacement;
        }

        /*
         * Prints the binary search tree
        */
        public void PrintTree()
        {
            if (root == null)
            {
                Console.WriteLine("tree is null");
            }
            else
            {
                Console.Write("[ ");
                Print(root);
                Console.WriteLine("]");
            }
        }


        /*
         * This function traverses the binary search tree, using In Order Traversal
         * Used in the PrintTree() function
        */
        private void Print(BtreeNode node)
        {
            if (node.LeftChld != null)
            {
                Print(node.LeftChld);
            }
            Console.Write(node.data + " ");
            if (node.RightChld != null)
            {
                Print(node.RightChld);
            }
        }
    }
}

/*
class Program
{
    static void Main ()
    {
        BinarySearchTree3102.BinaryTree bst = new BinarySearchTree3102.BinaryTree();

        for(int i = 0; i < 100; i++)
        {
            int j = new Random().Next(0, 100);
            bst.Add(j);
        }

        bst.Remove(30);

        bst.PrintTree();
        Console.WriteLine(bst.root.data);
    }
}
*/