Inorder traversal over BST returns a sorted array.


  • 0
    A

    Simple solution, exploiting inorder traversal property,
    Runtime: 5 ms

    public class BSTIterator {
        List<TreeNode> internalDS;
        Iterator<TreeNode> iterator;
        public BSTIterator(TreeNode root) {
            internalDS = new ArrayList<>();
            updateInternalDS(root);
            iterator = internalDS.iterator();
        }
        
        // Inorder traversal
        private void updateInternalDS(TreeNode root){
            if(root == null) return;
            updateInternalDS(root.left);
            internalDS.add(root);
            updateInternalDS(root.right);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return iterator.hasNext();
        }
    
        /** @return the next smallest number */
        public int next() {
            return iterator.next().val;
        }
    }
    
    

Log in to reply
 

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