package com.freetymekiyan.algorithms.level.medium;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a
 * BST.
 * <p>
 * Calling next() will return the next smallest number in the BST.
 * <p>
 * Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
 * <p>
 * Company Tags: LinkedIn, Google, Facebook, Microsoft
 * Tags: Tree, Stack, Design
 * Similar Problems: (M) Binary Tree Inorder Traversal, (M) Flatten 2D Vector, (M) Zigzag Iterator, (M) Peeking
 * Iterator, (M) Inorder Successor in BST
 */
public class BinarySearchTreeIterator {

    Deque<TreeNode> stack;

    /**
     * Push all left children into a Stack.
     * Actually these are all roots of left subtrees.
     */
    public BinarySearchTreeIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        pushAll(root);
    }

    /**
     * If the stack is empty, there is no more node left.
     */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /**
     * To get the next smallest value.
     * We pop the leftmost leaf from the stack.
     * Then we add all its right child's left children to stack.
     * Imagine all left children of a node is popped out.
     * The next will be itself.
     * And the next will be its right child's leftmost child.
     */
    public int next() {
        TreeNode n = stack.pop();
        pushAll(n.right); // Push all left subtrees of right child.
        return n.val;
    }

    void pushAll(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
}

@@ -823,97 +823,95 @@
   * 
-Push all left children into a Stack.%0A     * Actually these are all roots of left subtrees
+Simulate in order traversal.%0A     * Push all left children into a Stack to get prepared
 .%0A  
@@ -1192,160 +1192,8 @@
 /**%0A
-     * To get the next smallest value.%0A     * We pop the leftmost leaf from the stack.%0A     * Then we add all its right child's left children to stack.%0A
     
@@ -1212,24 +1212,23 @@
 ll left 
-children
+subtree
  of a no
@@ -1288,16 +1288,21 @@
   * And 
+then 
 the next
@@ -1324,30 +1324,103 @@
 ght 
-child's leftmost child
+subtree.%0A     * The right subtree repeats the pattern of pushing all left children into a stack
 .%0A  
@@ -1512,26 +1512,17 @@
 ht); // 
-Push all l
+L
 eft subt
@@ -1528,24 +1528,50 @@
 tree
-s of right child
+ and root is done. Repeat on right subtree
 .%0A  
@@ -1601,16 +1601,24 @@
  %7D%0A%0A    
+private 
 void pus

update Binary Search Tree Interator