Java amortized O(1) time, O(1) space solution


  • 0
    J

    Using Morris Traversal

    public class BSTIterator {
        
        private TreeNode root;
    
        private void process() {
            while (root != null && root.left != null) {
                TreeNode next = root.left;
                while (next.right != null && next.right != root) next = next.right;
                if (next.right == root) {
                    next.right = null;
                    return;
                } else {
                    next.right = root;
                    root = root.left;
                }
            }
        }
        
        public BSTIterator(TreeNode root) {
            this.root = root;
            process();
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return root != null;
        }
    
        /** @return the next smallest number */
        public int next() {
            if (!hasNext()) return -1;
            int res = root.val;
            root = root.right;
            process();
            return res;
        }
    }
    

Log in to reply
 

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