BST iterator

fishercoder1534 · fishercoder1534 · commit b00d05c2b0b0 · 2016-08-07T09:06:20.000-07:00
diff --git a/Common/src/utils/CommonUtils.java b/Common/src/utils/CommonUtils.java
@@ -140,4 +140,13 @@ public static void print(List<String> list) {
         System.out.println();
     }
 
+    public static void printIntegerList(List<List<Integer>> res) {
+        for(List<Integer> list : res){
+            for(int i : list){
+                System.out.print(i + ", ");
+            }
+            System.out.println();
+        }
+    }
+
 }
diff --git a/MEDIUM/src/medium/BSTIterator_using_q.java b/MEDIUM/src/medium/BSTIterator_using_q.java
@@ -0,0 +1,45 @@
+package medium;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+import classes.TreeNode;
+
+/**173. Binary Search Tree Iterator  QuestionEditorial Solution  My Submissions
+Total Accepted: 56053
+Total Submissions: 154876
+Difficulty: Medium
+Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
+
+Calling next() will return the next smallest number in the BST.
+
+Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.*/
+public class BSTIterator_using_q {
+    
+    private Queue<Integer> q;
+    
+    /**My natural idea is to use a queue to hold all elements in the BST, traverse it while constructing the iterator, although
+     * this guarantees O(1) hasNext() and next() time, but it uses O(n) memory.*/
+    //Cheers! Made it AC'ed at first shot! Praise the Lord! Practice does make perfect!
+    //I created a new class to do it using Stack to meet O(h) memory: {@link medium.BSTIterator_using_stack}
+    public BSTIterator_using_q(TreeNode root) {
+        q = new LinkedList<Integer>();
+        if(root != null) dfs(root, q);
+    }
+
+    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);
+    }
+
+    /** @return whether we have a next smallest number */
+    public boolean hasNext() {
+        return !q.isEmpty();
+    }
+
+    /** @return the next smallest number */
+    public int next() {
+        return q.poll();
+    }
+}
diff --git a/MEDIUM/src/medium/BSTIterator_using_stack.java b/MEDIUM/src/medium/BSTIterator_using_stack.java
@@ -0,0 +1,45 @@
+package medium;
+
+import java.util.Stack;
+
+import classes.TreeNode;
+
+/**173. Binary Search Tree Iterator  QuestionEditorial Solution  My Submissions
+Total Accepted: 56053
+Total Submissions: 154876
+Difficulty: Medium
+Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
+
+Calling next() will return the next smallest number in the BST.
+
+Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.*/
+public class BSTIterator_using_stack {
+    /**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_using_stack(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;
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -140,4 +140,13 @@ public static void print(List<String> list) {`
`140`	`140`	`System.out.println();`
`141`	`141`	`}`
`142`	`142`
	`143`	`+ public static void printIntegerList(List<List<Integer>> res) {`
	`144`	`+ for(List<Integer> list : res){`
	`145`	`+ for(int i : list){`
	`146`	`+ System.out.print(i + ", ");`
	`147`	`+ }`
	`148`	`+ System.out.println();`
	`149`	`+ }`
	`150`	`+ }`
	`151`	`+`
`143`	`152`	`}`