JAVA Solution Using a BST Iterator


  • 0
    X

    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
            pushNodes(root);
            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) {
                pushNodes(node.right);
            }
            return node.val;
        }
        
        public void pushNodes(TreeNode node) {
            while (node != null) {
                stack.push(node);
                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.