/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;

/* Name of the class has to be "Main" only if the class is public. */
    class BinarySearchTree {
        TreeNode mRoot = null;

        static private class TreeNode {
            TreeNode(int value, TreeNode parent) {
                this.value = value;
                this.parent = parent;
            }

            TreeNode parent, left, right;
            int value;
        }

        public TreeNode successor(TreeNode node) {
            if (node == null)
                return node;

            if (node.right != null) {
                return leftMostNode(node.right);
            }

            while (null != node.parent /* while we are not root */
                    && node.parent.right == node) {

                node = node.parent; // go one level up
            }

            return node.parent;
        }

        public static TreeNode leftMostNode(TreeNode node) {
            if (null == node) {
                return null;
            }

            while (null != node.left) {
                node = node.left;
            }
            return node;
        }

        /** Search value in Tree need for Successor **/
        public TreeNode search(int key) {
            TreeNode node = mRoot;
            while (node != null 
                    && key != node.value) {

                if (key < node.value) {
                    node = node.left;
                } else if (key > node.value) {
                    node = node.right;
                }
            }
            return node;
        }

        /** Returns Successor of given value **/
        public int getSuccessor(int val) {
            TreeNode node;
            if (null == (node = search(val))
                    || (null == (node = successor(node)))) {
                // either val is not in BST, or it is the last value-> no
                // successor
                return -1;// error_code for instance;
            }

            return node.value;
        }

        public BinarySearchTree(int[] array) {
            for (int elem : array) {
                add(elem);
            }
        }

        public void add(int value) {
            if (mRoot == null) {
                mRoot = new TreeNode(value, null);
            } else {
                insert(mRoot, value);
            }
        }

        void insert(TreeNode node, int value) {
            if (node == null)
                return;

            if (value < node.value) {
                if (node.left == null) { // insert as the new left node
                    node.left = new TreeNode(value, node);
                } else { // insert in the left subtree
                    insert(node.left, value);
                }
            } else { // value >= node.value
                if (node.right == null) {
                    node.right = new TreeNode(value, node);
                } else {
                    insert(node.right, value);
                }
            }
        }
        
        public static void main(String[] args) {

            BinarySearchTree bst = 
                new BinarySearchTree(new int[]{30, 10, 45, 38, 20, 50, 25, 33, 8, 12});
        
            int value = 8; // first one
            while (value != -1) {
                System.out.println("next for " + value + " is " +
                    (value = bst.getSuccessor(value)));
            }
        }
    }