The similarity between this question and BST inorder traversal


  • 0
    F

    The implementation of BST iterator is very similar to binary search tree Inorder traversal. Inorder using stack and two while loop. However, in the iterator, the first while condition become hasNext() and the code inside the first while condition become next().
    For your reference, It is the code of binary search tree Inorder traversal.

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack();
            List<Integer> res = new ArrayList();
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
            return res;
        }
    }
    

    And below is the BST iterator.

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

Log in to reply
 

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