public class MTFBinaryTree extends BinaryTree implements Tree{


        private Node root;
        private int size;

        public MTFBinaryTree() {
            // Initialize the size to zero.
            this.size = 0;
        }


        public int size() {
            // Just return the size.
            return this.size;
        }


        public Node insertRoot(int k, String v) {
            // TODO Implement the insertion at root method.
            insertLeaf(k, v);
            Node w = get(k);
            return insertRoot(w);
        }

        private Node insertRoot(Node n)
        {
            if(n == root)
                return n;
            else
            {
                while(n != root)
                {
                    rotate(n);
                }
                return n;
            }
        }

        public void rotate (Node n)
        {
            if (n.getKey() < n.getParent().getKey())
            {
                rotateRight(n);
            }
            else
            {
                rotateLeft(n);
            }
        }

        public void rotateRight(Node n) {
            if (n.getParent() == root) {
                Node r = n.getRight();
                n.setRight(n.getParent());
                root = n;
                root.getRight().setLeft(r);
            } else {
                Node p = n.getParent();
                Node r = n.getRight();
                n.setParent(p.getParent());
                n.setRight(p);
                p.setLeft(r);
            }
        }

        public void rotateLeft(Node n) {
            if (n.getParent() == root) {
                Node l = n.getLeft();
                n.setLeft(n.getParent());
                root = n;
                root.getLeft().setRight(l);
            } else {
                Node p = n.getParent();
                Node l = n.getLeft();
                n.setParent(p.getParent());
                n.setLeft(p);
                p.setRight(l);
            }
        }

        public void recursiveInsertLeaf(Node current, Node newNode) {
            // Check whether the node is less than or greater than or equal
            // to the node we are inserting.
            int compare = newNode.compareTo(current);

            // If less than, try to insert it to the left, or recurse to the left
            // subtree.
            if (compare < 0) {
                if (current.getLeft() == null) {
                    current.setLeft(newNode);
                    size++;
                }
                else
                    recursiveInsertLeaf(current.getLeft(), newNode);
                // If equal, ignore. We just ignore duplicates.
            } else if (compare == 0) {
                return;
                // If greater than, try to insert to the left, or recurse to the
                // right subtree.
            } else {
                if (current.getRight() == null) {
                    current.setRight(newNode);
                    size++;
                }
                else
                    recursiveInsertLeaf(current.getRight(), newNode);
            }
        }

        public Node insertLeaf(int k, String v) {
            // Create a new node, representing the key-value pair
            Node n = new BTNode(k, v);

            // If the tree doesn't have a root, insert at the root.
            if (this.root == null) {
                this.root = n;
                size++;
                return n;
            }

            // Otherwise, recursively find the correct location to insert.
            recursiveInsertLeaf(this.root, n);

            // Return the newly inserted node.
            return n;
        }

        public Node recursiveGet(int k, Node n) {
            // Base Case - Null Node
            if (n == null)
                return null;

            int currentKey = n.getKey();
            Node temp = n;

            // Check if the key matches the node we are looking at.
            if (k == currentKey)
            {
                if(n == root)
                    return n;
                else
                {
                    while(n != root)
                    {
                        rotate(n);
                    }
                }
                return temp;
            }
            // If the key is less than what we are looking for, recurse to the left subtree,
            else if (k < currentKey)
                return recursiveGet(k, n.getLeft());
            // Otherwise, recurse to the right subtree.
            else
                return recursiveGet(k, n.getRight());
        }

        public Node get(int k) {
            // Use the recursive method to get the value associated with a key.
            return recursiveGet(k, this.root);
        }

        public int recursiveFind(int k, Node n) {
            // Base Case - Null Node
            if (n == null)
                return -1;

            int currentKey = n.getKey();
            int result = 1;

            // Check if the key at this node is the one we are looking for.
            if (k == currentKey)
            {
                if(n == root)
                    return 1;
                else
                {
                    while(n != root)
                    {
                        rotate(n);
                    }
                }
                return 1;
            }
            // If the key is less than the current node, recurse to the left.
            else if (k < currentKey)
                result = recursiveFind(k, n.getLeft());
            // Otherwise, we recurse to the right.
            else
                result = recursiveFind(k, n.getRight());

            if (result == -1)
                // We didn't find the node we are looking for, return -1.
                return -1;
            else
                // Return the number of steps it took to find the current node.
                return 1+result;
        }

        public int find(int k) {
            // We use a recursive find method, passing the root in
            // as the first argument.
            // We need to return the number of comparisons made.
            return recursiveFind(k, this.root);
        }


        public void remove(Node n) {
            // TODO Implement the removal method
            if (n == null)
                    return;


            // leaf
            else if (n.getLeft() == null && n.getRight() == null)
            {
                if(n.getParent().getLeft() == n)
                    n.getParent().setLeft(null);
                else {
                    n.getParent().setRight(null);}
                n = null;
            }
            //1 child
            else if (n.getLeft() == null && n.getRight() != null)
            {
                    Node p = n.getParent();
                    Node r = n.getRight();
                    r.setParent(p);
                    n = null;
                    size--;
            }
            else if (n.getLeft() != null && n.getRight() == null)
            {
                    Node p = n.getParent();
                    Node r = n.getLeft();
                    r.setParent(p);
                    n = null;
                    size--;
            }


            //root
            else if (n.getParent() == null)
            {
                    Node left = n.getLeft();
                    Node temp = inorderSuccessor(n);
                    remove(temp);
                    Node right = n.getRight();

                    root = temp;
                    root.setLeft(left);
                    root.setRight(right);
                    n = null;
                    size--;
            }

            //2children
            else
            {
                    Node left = n.getLeft();
                    Node temp = inorderSuccessor(n);
                    remove(inorderSuccessor(n));
                    Node right = n.getRight();

                    if(n.getParent().getLeft() == n)
                            n.getParent().setLeft(temp);
                    else
                            n.getParent().setRight(temp);
                    temp.setLeft(left);
                    temp.setRight(right);
                    n = null;
                    size--;


            }
    }

        public Node inorderSuccesor(Node v){

            if (v.getRight() != null)
            {
                Node w = v.getRight();
                while (w.getLeft() != null)
                {
                    w = w.getLeft();
                }
                return w;
            }
            else
            {
                Node p = v.getParent();
                Node c = v;
                while (c != p.getLeft())
                {
                    c = p;
                    p = p.getParent();
                }
                return p;
            }
        }


        private void recursivePrintTree(Node n) {
            // Base Case - Null Node
            if (n == null)
                return;

            Node left = n.getLeft();
            Node right = n.getRight();

            // If there is a left child, print out the connection and
            // recurse.
            if (left != null) {
                System.out.println(n.getKey() + " -- " + left.getKey() + ";");
                recursivePrintTree(left);
            }
            // If there is a right child, print out the connection and
            // recurse.
            if (right != null) {
                System.out.println(n.getKey() + " -- " + right.getKey() + ";");
                recursivePrintTree(right);
            }
        }

        public void printTree() {
            // Print out the surrounding structure for the
            // graphviz format.
            System.out.println("graph {");
            // Recursively print out the structure of the tree by an pre-order
            // traversal
            recursivePrintTree(this.root);
            System.out.println("}");
        }

        public Node getRoot() {
            // Just return the root, or null if there is no root.
            return this.root;
        }

    }