My simple java solution (using stack)


  • 0
    L
    public class BSTIterator {
    
        private Deque<TreeNode> stack;
        
        public BSTIterator(TreeNode root) {
            stack = new LinkedList<>();
            mostLeft(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {        
            TreeNode cur = stack.pop();
            mostLeft(cur.right);
            return cur.val;
        }
        
            /** traverse to the left most node from given node
        and put all nodes onto stack along the way */
        private void mostLeft(TreeNode root) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
        }
    }
    

Log in to reply
 

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