KthSmallestElementInABST230

fluency03 · fluency03 · commit df95d0f2b468 · 2018-01-27T16:19:02.000+01:00
diff --git a/README.md b/README.md
@@ -32,11 +32,11 @@
 
 
 
-# Total: 134
+# Total: 135
 
 | Easy | Medium | Hard |
 |:----:|:------:|:----:|
-|  23  |   84   |  27  |
+|  23  |   85   |  27  |
 
 
 | Question | Solution | Difficulty |
@@ -132,6 +132,7 @@
 | [221. Maximal Square](https://leetcode.com/problems/maximal-square/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/MaximalSquare221.java) | Medium |
 | [224. Basic Calculator](https://leetcode.com/problems/basic-calculator/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/BasicCalculator224.java) | Hard |
 | [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/InvertBinaryTree226.java) | Easy |
+| [230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/KthSmallestElementInABST230.java) | Medium |
 | [233. Number of Digit One](https://leetcode.com/problems/number-of-digit-one/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/NumberOfDigitOne233.java) | Hard |
 | [240. Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/SearchA2DMatrixII240.java) | Medium |
 | [241. Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/DifferentWaysToAddParentheses241.java) | Medium |
diff --git a/src/KthSmallestElementInABST230.java b/src/KthSmallestElementInABST230.java
@@ -0,0 +1,63 @@
+/**
+ * Given a binary search tree, write a function kthSmallest to find the kth
+ * smallest element in it.
+ *
+ * Note:
+ * You may assume k is always valid, 1 &le; k &le; BST's total elements.
+ *
+ * Follow up:
+ * What if the BST is modified (insert/delete operations) often and you need to
+ * find the kth smallest frequently? How would you optimize the kthSmallest
+ * routine?
+ *
+ */
+
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+
+
+public class KthSmallestElementInABST230 {
+    public int kthSmallest(TreeNode root, int k) {
+        Stack<Integer> st = new Stack<>();
+        kthSmallest(root, k, st);
+        return st.pop();
+    }
+
+    public void kthSmallest(TreeNode root, int k, Stack<Integer> st) {
+        if (root == null) return;
+
+        kthSmallest(root.left, k, st);
+        if (st.size() == k) return;
+
+        st.push(root.val);
+        if (st.size() == k) return;
+
+        kthSmallest(root.right, k, st);
+    }
+
+
+    public int kthSmallest2(TreeNode root, int k) {
+        int[] i = new int[]{0, 0};
+        kthSmallest(root, k, i);
+        return i[1];
+    }
+
+    public void kthSmallest(TreeNode root, int k, int[] i) {
+        if (root.left != null) kthSmallest(root.left, k, i);
+        if (i[0] == k) return ;
+
+        i[0] = i[0] + 1;
+        i[1] = root.val;
+        if (i[0] == k) return;
+
+        if (root.right != null) kthSmallest(root.right, k, i);
+    }
+
+}
