Java solution O(n) time complexity, O(height) space complexity


#1

public int kthsmallest(TreeNode A, int B) {
BSTIterator iterator = new BSTIterator(A);
while (iterator.hasNext()) {
B–;
if (B == 0) {
break;
}
iterator.next();
}

    return iterator.getVal();
}

 class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        fillStack(root);
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return stack.size() > 0;
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode node = stack.pop();
        fillStack(node.right);
        return node.val;
    }

    private void fillStack(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public int getVal() {
        return stack.peek().val;
    }
}