Java solution with explanation


  • 0
    L

    This includes iterative inorder traversal using a stack. The requirement is to hold the stack into memory to manage O(h) space complexity. So traverse as required by printing the root and traversing to its left.

    public class BSTIterator {
        private final Stack<TreeNode> stack = new Stack<>();
        
        public BSTIterator(TreeNode root) {
            if(root==null) {
                return;
            }     
                
            TreeNode n = root;
            while(n!=null) {
                stack.push(n);
                n = n.left;
            }                       
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            if(!hasNext()) {
                return -1;
            }
            int ret = -1;
            if(!stack.isEmpty()) {
                TreeNode n = stack.pop();
                ret = n.val;
                n = n.right;
                while(n!=null) {
                    stack.push(n);
                    n = n.left;
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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