package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class _173 {

    public static class Solution1 {

        public static class BSTIterator {
            private Queue<Integer> queue;

            public BSTIterator(TreeNode root) {
                queue = new LinkedList<>();
                if (root != null) {
                    dfs(root, queue);
                }
            }

            private void dfs(TreeNode root, Queue<Integer> q) {
                if (root.left != null) {
                    dfs(root.left, q);
                }
                q.offer(root.val);
                if (root.right != null) {
                    dfs(root.right, q);
                }
            }

            public boolean hasNext() {
                return !queue.isEmpty();
            }

            public int next() {
                return queue.poll();
            }
        }
    }

    public static class Solution2 {
        public static class BSTIterator {
            /**
             * This is a super cool/clever idea: use a stack to store all the current left nodes of the BST, when pop(), we
             * push all its right nodes into the stack if there are any.
             * This way, we use only O(h) memory for this iterator, this is a huge saving when the tree is huge
             * since h could be much smaller than n. Cheers!
             */

            private Stack<TreeNode> stack;

            public BSTIterator(TreeNode root) {
                stack = new Stack();
                pushToStack(root, stack);
            }

            private void pushToStack(TreeNode root, Stack<TreeNode> stack) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
            }

            public boolean hasNext() {
                return !stack.isEmpty();
            }

            public int next() {
                TreeNode curr = stack.pop();
                pushToStack(curr.right, stack);
                return curr.val;
            }
        }
    }
}

@@ -78,16 +78,40 @@
 eNode;%0A%0A
+import java.util.Deque;%0A
 import j
@@ -2203,11 +2203,875 @@
  %7D%0A    %7D
+%0A%0A    public static class Solution3 %7B%0A        /**%0A         * credit: https://leetcode.com/problems/binary-search-tree-iterator/discuss/52647/Nice-Comparison-(and-short-Solution%0A         */%0A        public static class BSTIterator %7B%0A            Deque%3CTreeNode%3E stack;%0A            TreeNode visit;%0A%0A            public BSTIterator(TreeNode root) %7B%0A                stack = new LinkedList%3C%3E();%0A                visit = root;%0A            %7D%0A%0A            public int next() %7B%0A                while (visit != null) %7B%0A                    stack.addLast(visit);%0A                    visit = visit.left;%0A                %7D%0A                TreeNode next = stack.pollLast();%0A                visit = next.right;%0A                return next.val;%0A            %7D%0A%0A            public boolean hasNext() %7B%0A                return visit != null && !stack.isEmpty();%0A            %7D%0A        %7D%0A    %7D
 %0A%7D%0A

add a solution for 173