Java Solution with O(1) time and O(h) space complexities ON AVERAGE


  • 0
    D

    Below is the java solution.
    At the first glance, the algorithm run in O(h) time & O(h) space. But if you take a closer look at the problem, you will see that it asks for "on average".
    We see that, for the function next, each node is popped on to the stack exactly 1 time. Hence, on average, it is O(1) time complexity.

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

  • 6
    T
    My Java code, same idea with above.
    
    public class BSTIterator {
      Stack<TreeNode> s = new Stack<TreeNode>();
      public BSTIterator(TreeNode root) {
          findMin(root);
      }
    
      /** @return whether we have a next smallest number */
      public boolean hasNext() {
          return !s.empty();
      }
    
      /** @return the next smallest number */
      public int next() {
          TreeNode nextMin = s.pop();
          findMin(nextMin.right);
        
          return nextMin.val;
      }
    
      private void findMin(TreeNode n) {
          while(n != null) {
              s.push(n);
              n = n.left;
          }
      }
    }

Log in to reply
 

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