Simple and efficient Java solution by DFS + Queue


  • 1
    L
    public class BSTIterator {
        private Queue<Integer> queue = new LinkedList<Integer>();
        
        public BSTIterator(TreeNode root) {
            dfsTree(root);
        }
        
        private void dfsTree(TreeNode node) {
            if( node != null) {
                dfsTree(node.left);
                queue.add(node.val);
                dfsTree(node.right);
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !queue.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            if( hasNext() ) {
                return queue.remove();
            }
            else {
                return 0;
            }
        }
    }
    

  • 0
    M

    @laqxs Isn't this using O(n) memory where n is the number of nodes in the tree?


  • 0
    L

    @manu5 Yes, I believe it's space complexity is O(n) as I put all values of nodes into the queue.


Log in to reply
 

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