java solution with nested iterator

  • 2
    public class BSTIterator {
    private BSTIterator runner;  // the nested iterator.
    private boolean rootYielded=false;  // if root value has already been yielded.
    private TreeNode root;   // store the root node.
    public BSTIterator(TreeNode root) {
            if(root==null) return;
            runner= new BSTIterator(root.left);
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
            if(runner==null) return false;
            if(runner.hasNext()) return true;
            if(rootYielded) return false;
            return true;
    /** @return the next smallest number */
    public int next() {
            if(runner==null) return 0;
            if(runner.hasNext()) return;
            if(rootYielded) return 0;
            runner = new BSTIterator(root.right);
            return root.val;

    The recursion is easy to understand. It works by first iterating its left subtree, then yield itself, and then iterating its right subtree.

  • 0
    This post is deleted!

  • 0

    Recursion depth is no bigger than the highest path at any time, already iterated parts loses reference and gets garbage collected. Thus space complexity is O(h).

    As to time complexity, I admit it takes O(h) steps, because we need to go in the deepest level of recursion every time. But if you examine more carefully, all the other solutions in this forum also need average O(h) steps. The constant factor is extremely small though. and you know that the difference between O(h) -- or O(log n) -- and O(1) is very small (compared with the difference between O(1) and O(n)).

Log in to reply

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