import java.util.Stack;

public class OrderedBSTreeResha {
    Node root;
    Stack<Integer> stack = new Stack<Integer>();
    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;
        }
    }

    // Root of BST



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

    public int getMax() {

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

    public boolean delete(int val){

        try {
            if (deletion(root, val) != null) {
                stack.pop();
                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;
    }

    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);
            stack.push(val);
        } else if (val > root.val) {
            root.right = insertion(root.right, val);
            stack.push(val);
        }

        return root;

    }

    public int removeLast(){
        int temp = stack.peek();
        delete(temp);
        stack.pop();
        return stack.peek();
    }
    public int getLast() {
        return stack.peek();
    }

    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
        OrderedBSTreeResha tree = new OrderedBSTreeResha();
        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

    }
}