Very clear and easy to understand Java solution based on In-Order DFS learned from Algorithms class.


  • 0
    G
    public class BSTIterator {
    	private TreeNode head = null;
    	private Stack<Integer> stack = new Stack<>();
        public BSTIterator(TreeNode root) {
            head = root;
            DFS(head,stack);//in-order DFS;
        }
        
        private void DFS(TreeNode root, Stack<Integer> stack){
        	if(root==null) return;
        	//notice we need the top of the stack to have the smallest num so far;
        	DFS(root.right, stack);
        	stack.push(root.val);
        	DFS(root.left, stack);
        }
        
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if(!stack.isEmpty()) return true;
            else return false;
        }
    
        /** @return the next smallest number */
        public int next() {
            return stack.pop();
        }
    }

Log in to reply
 

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