import java.util.NoSuchElementException;

public class AVLTree {

    private Node root;
    
    public AVLTree() {
        this.root = null;
    }

    private static class Node {
        int value;
        Node left;
        Node right;
        int height;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
            height = 0;
        }
        
        public Node(int value) {
            this(value, null, null);
        }
    }
    
    // Helper function to get the height of a node in
    // an AVL tree. Handles the case of null trees
    // having height -1 for the purposes of calculating balance
    private static int height(Node t) {
        if (t == null) {
            return -1;
        } else {
            return t.height;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(int value) {
        return contains(value, root);
    }

    private boolean contains(int value, Node t) {
        if (t == null) {
            return false;
        }
        if (value < t.value) {
            return contains(value, t.left);
        } else if (value > t.value) {
            return contains(value, t.right);
        } else {
            return true;
        }
    }

    public int findMin() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return findMin(root).value;
    }

    // An example of recursively finding the min
    private Node findMin(Node t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    public int findMax() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return findMax(root).value;
    }

    // An example of iteratively finding the max
    private Node findMax(Node t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }

    public void insert(int value) {
        root = insert(value, root);
    }

    private Node insert(int value, Node t) {
        if (t == null) {
            return new Node(value);
        }
        if (value < t.value) {
            t.left = insert(value, t.left);
        } else if (value > t.value) {
            t.right = insert(value, t.right);
        } else {
            // Do nothing - nodes are unique
        }
        return balance(t); // For a plain BST this line would be "return t;"
    }
    
    
    /**
     * Uses tree rotation (if necessary) to re-balance the subtree rooted
     * at t. This operation should be O(1). At the end of this function, the
     * height field of node t and all of its descendants must be correct.
     * @param t the root of the subtree to be balanced
     * @return A balanced subtree containing the same nodes as the original subtree
     */
    private Node balance(Node t) {
        if (t == null) {
            return t;
        }
        
        if (/* TODO: condition for subtree too tall */) {
            
            if (/* TODO: Condition for left-right case (kink case) */ ) {
                // TODO: Turn into left-left case (line case)
            }
            
            //TODO: Handle left-left case 
        } else if (/* TODO: condition of right subtree too tall*/) { 
            
            if (// TODO: Condition for right-left case (kink case)) {
                // TODO: Make into right-right case (line case)
            }
            
            // TODO -  Handle right-right case (line case)
        }
        // TODO: Any extra work necessary to correct the tree
        return t;
    }
    
    private Node rotateLeft(Node t) {
     /*
      * TODO: Implement a left rotation. The diagram below illustrates an example.
        t               x
       / \             / \
      a   x   ===>    t   c
         / \         / \  
        b   c       a   b     
     */
    }
    
    private Node rotateRight(Node t) {
        // TODO - Implement a right rotation
    }

    public int remove(int value) {
        return remove(value, this.root).value;
    }

    // This differs from the version we worked on in class in that it
    // does not use lazy deletion.
    private Node remove(int value, Node t) {
        if (t == null) {
            return t;
        }
        if (value < t.value) {
            t.left = remove(value, t.left);
        } else if (value > t.value) {
            t.right = remove(value, t.right);
        } else if (t.left != null && t.right != null) {
            t.value = findMin(t.right).value;
            t.right = remove(t.value, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return balance(t); // For a plain BST this line would be "return t;"
    }
}