javabst.java

/*
 * Complete the function below.
 */
    
    static private class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;	
        
        public TreeNode(int n){
            this.val = n;
            left = null;
            right = null;
        }
    }

    static private class BST {
        TreeNode root;
        
        public BST() {
            root = null;
        }
        
        boolean empty() {
            return root == null;
        }
        
        int insert(int k) {
            if (root == null) {
                root = new TreeNode(k);
                return 0;                
            }
                
            int counter = 0;
            TreeNode n = root;
            while (true) {
                ++counter;
                if (k < n.val) {
                    if (n.left == null) {
                        n.left = new TreeNode(k);
                        break;
                    } else {
                        n = n.left;
                    }
                } else {
                    if (n.right == null) {
                        n.right = new TreeNode(k);
                        break;
                    } else {
                        n = n.right;
                    }
                }
            }
            
            return counter;
        }
    }

    static void createBST(int[] keys) {
        int counter = 0;
        BST bst = new BST();
        for (int k : keys) {
            counter += bst.insert(k);
            System.out.println(counter);
        }
        
    }