[Stack] Add a solution to Binary Search Tree Iterator

soapyigu · soapyigu · commit 07e16a40a973 · 2019-12-28T16:02:07.000-08:00
diff --git a/README.md b/README.md
@@ -4,7 +4,7 @@
 ![Leetcode](./logo.png?style=centerme)
 
 ## Progress
-[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 310 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
+[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 311 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
 
 ## Contributors
 
@@ -169,6 +169,7 @@
 [Ternary Expression Parser](https://leetcode.com/problems/ternary-expression-parser/)| [Swift](./Stack/TernaryExpressionParser.swift)| Medium| O(n)| O(n)|
 [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)| [Swift](./Stack/PreorderTraversal.swift)| Medium| O(n)| O(n)|
 [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)| [Swift](./Stack/InorderTraversal.swift)| Medium| O(n)| O(n)|
+[Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)| [Swift](./Stack/BinarySearchTreeIterator.swift)| Medium| O(n)| O(n)|
 [Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)| [Swift](./Stack/PostorderTraversal.swift)| Hard| O(n)| O(n)|
 [Decode String](https://leetcode.com/problems/decode-string/)| [Swift](./Stack/DecodeString.swift)| Medium| O(n)| O(n)|
 
@@ -716,7 +717,7 @@
 |	[Swift](./String/ReverseWordsStringII.swift)	|	186	|	[Reverse Words in a String II](https://oj.leetcode.com/problems/reverse-words-in-a-string-ii/) &hearts;	| Medium	|
 |	[Swift]((./Sort/LargestNumber.swift))	|	179	|	[Largest Number](https://oj.leetcode.com/problems/largest-number/)	| Medium	|
 |		|	174	|	[Dungeon Game](https://oj.leetcode.com/problems/dungeon-game/)	| Hard	|
-|		|	173	|	[Binary Search Tree Iterator](https://oj.leetcode.com/problems/binary-search-tree-iterator/)	| Medium	|
+|	[Swift](./Stack/BinarySearchTreeIterator.swift)	|	173	|	[Binary Search Tree Iterator](https://oj.leetcode.com/problems/binary-search-tree-iterator/)	| Medium	|
 |	[Swift](./Math/FactorialTrailingZeroes.swift)	|	172	|	[Factorial Trailing Zeroes](https://oj.leetcode.com/problems/factorial-trailing-zeroes/)	| Easy	|
 |	[Swift](./Math/ExcelSheetColumnNumber.swift)	|	171	|	[Excel Sheet Column Number](https://oj.leetcode.com/problems/excel-sheet-column-number/)	| Easy	|
 |	[Swift](./Array/TwoSumIII.swift)	|	170	|	[Two Sum III - Data structure design](https://oj.leetcode.com/problems/two-sum-iii-data-structure-design/) &hearts;	| Easy	|
diff --git a/Stack/BinarySearchTreeIterator.swift b/Stack/BinarySearchTreeIterator.swift
@@ -0,0 +1,58 @@
+/**
+ * Question Link: https://leetcode.com/problems/binary-search-tree-iterator/
+ * Primary idea: In order iteration using a stack.
+ * Time Complexity: O(n), Space Complexity: O(n)
+ *
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+
+class BSTIterator {
+    
+    var stack: [TreeNode]
+
+    init(_ root: TreeNode?) {
+        stack = [TreeNode]()
+        
+        loadAllLeftToStack(from: root)
+    }
+    
+    /** @return the next smallest number */
+    func next() -> Int {
+        let node = stack.removeLast()
+        
+        loadAllLeftToStack(from: node.right)
+        
+        return node.val
+    }
+    
+    /** @return whether we have a next smallest number */
+    func hasNext() -> Bool {
+        return !stack.isEmpty
+    }
+    
+    private func loadAllLeftToStack(from root: TreeNode?) {
+        var node = root
+        
+        while let current = node {
+            stack.append(current)
+            node = current.left
+        }
+    }
+}
+
+/**
+ * Your BSTIterator object will be instantiated and called as such:
+ * let obj = BSTIterator(root)
+ * let ret_1: Int = obj.next()
+ * let ret_2: Bool = obj.hasNext()
+ */
