Java solution using both stack and recursion with explanation


  • 0
    L
    public class BSTIterator {
        private Queue<Integer> queue;
    
        public BSTIterator(TreeNode root) {
          queue = inorderTraversal(root);
          //Enable following two lines if using recursion.
          //queue = new LinkedList<>();
          //inorder(root,queue);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !queue.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            if(!queue.isEmpty()) {
                return queue.poll();
            }
            return -1;
        }
        
        private void inorder(TreeNode root, Queue<Integer> q) {
            if(root==null) {
                return;
            }
            inorder(root.left,q);
            q.add(root.val);
            inorder(root.right,q);
        }
        
        
        private Queue<Integer> inorderTraversal(TreeNode root) {
            Queue<Integer> list = new LinkedList<Integer>();
            if(root==null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            while(root!=null) {
                stack.push(root);
                root=root.left;
            }
            
            while(!stack.isEmpty()) {
                TreeNode temp = stack.pop();
                System.out.println(temp.val);
                list.add(temp.val);
                TreeNode right = temp.right;
                if(right!=null) {
                    stack.push(right);
                    TreeNode left = right.left;
                    while(left!=null) {
                        stack.push(left);
                        left = left.left;
                    }
                }
            }
            return list;
        }    
    }
    

Log in to reply
 

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