JAVA Solution Using a BST Iterator

  • 0

    Implementing a BST iterator using a stack. next() function will automatically push next node into the stack. Calling next() function k times will return 1st---kth smallest in order.

    class Solution {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        public int kthSmallest(TreeNode root, int k) {  //implement a BST iterator
            int target = Integer.MAX_VALUE;
            for (int i = 0; i < k; i++) {
                target = next();
            return target;
        public int next() {
            TreeNode node = stack.pop();
            if (node.right != null) {
            return node.val;
        public void pushNodes(TreeNode node) {
            while (node != null) {
                node = node.left;
            // the smallest is on top of the stack

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.