public class OrderedBSTree {
	//you may declare any variables here.
	class Node {
        int val;
        Node left, right;

        public Node(int item) {
            val = item;
            left = right = null;
        }
        public Node getLeft() {
            return left;
        }
        public Node getRight() {
            return right;
        }
        public void setLeft (Node left) {
            this.left = left;
        }
        public void setRight(Node right) {
            this.right = right;
        }
    }

	// Root of BST
    Node root;
    Stack<Integer> stack = new Stack<Integer>();


	/**
	 * return the last inserted element
	 * Runtime is O(1)
	 * @return
	 */
    public int getLast() {

    	return stack.peek();
    }


	/**
	 * return the min value of the tree.
	 * Runtime is ≤ O(lgN)
	 * @return
	 */

	public int getMin() {
		Node current = root;
		while (current.left != null) {
            current = current.left;
        }
        return (current.val);
	}

	/**
	 * return the max value of the tree.
	 * Runtime is ≤ O(lgN)
	 * @return
	 */
	public int getMax() {

			Node current = root;
			while (current.right != null) {
	            current = current.right;
	        }
	        return (current.val);
	}

	/**
	 * delete element from the tree.
	 * Runtime is ≤ O(lgN)
	 * @param val
	 * @return true if successfully removed. otherwise return false.
	 */
	public boolean delete(int val){

        try {
            if (deletion(root, val) != null) {
                return true;
            } else {
                return false;
            }
        }
        catch (Exception e){
            return false;
        }
    }

    private Node deletion(Node root, int val){
        if(val < root.val) root.left = deletion(root.left, val);
        else if(val > root.val) root.right = deletion(root.right, val);
        else
        {
            if(root.getLeft() == null && root.getRight() == null)
            {
                return null;
            }
            else if(root.getLeft() == null)
            {
                // node with one node (no left node)
                return root.getRight();
            }
            else if(root.getRight() == null)
            {
                // node with one node (no right node)
                return root.getLeft();
            }
        }
        return root;
    }

	/**
	 * insert element into the tree.
	 * Runtime is ≤ O(lgN)
	 * @param val
	 * @return true if successfully added. otherwise return false.
	 */

    boolean insert(int val) {

        if (insertion(root, val) == null) {
            return true;
        } else {

            root = insertion(root, val);
            return false;
        }
    }

    private Node insertion(Node root, int val) {

        if (root == null) {
            root = new Node(val);
            stack.push(val);
            return root;
        }
        if (val < root.val) {
            root.left = insertion(root.left, val);
            if(stack.peek() == val) {stack.pop();} //here
            stack.push(val);
        } else if (val > root.val) {
            root.right = insertion(root.right, val);
            if(stack.peek() == val) {stack.pop();} //here
            stack.push(val);
        }

        return root;

    }

	/**
	 * delete the last inserted element.
	 * Runtime is ≤ O(lgN)
	 * @return
	 */
	 public int removeLast() {
         return stack.pop();
    }

	public void inorder() {
        inorderRec(root);
    }

    // A utility function to do inorder traversal of BST
    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.println(root.val);
            inorderRec(root.right);
        }
    }

	public static void main(String[] args) throws Exception{
		//example1
		OrderedBSTree tree = new OrderedBSTree();
		tree.insert(15);
		tree.insert(12);
		tree.insert(10);
		tree.insert(29);
		tree.insert(5);
		tree.insert(100);
		tree.insert(100);
		System.out.println(tree.getMax()); 			//100
		System.out.println(tree.getLast());			//100
		System.out.println(tree.removeLast());		//100
		System.out.println(tree.delete(100)); 		//false
		System.out.println(tree.getLast());			//5
		System.out.println(tree.getMin()); 			//5
		System.out.println(tree.getMax()); 			//29
		System.out.println(tree.delete(12)); 		//true
		System.out.println(tree.delete(12)); 		//false
		System.out.println(tree.insert(10)); 		//false
		System.out.println(tree.root.val);
		System.out.println();
		tree.inorder();


	}
}