3 ways implemented in JAVA (Python): Binary Search, in-order iterative & recursive
Binary Search (dfs): (edited 1/2019) this is NOT preferrable as in performance but since the quesiton is categorized with Binary Search tag, I was trying to sol
Binary Search (dfs): (edited 1/2019) this is NOT preferrable as in performance but since the quesiton is categorized with Binary Search tag, I was trying to solve it in that way.\n- time complexity: O(N) best, O(N^2) worst\n\n      public int kthSmallest(TreeNode root, int k) {\n            int count = countNodes(root.left);\n            if (k <= count) {\n                return kthSmallest(root.left, k);\n            } else if (k > count + 1) {\n                return kthSmallest(root.right, k-1-count); // 1 is counted as current node\n            }\n            \n            return root.val;\n        }\n        \n        public int countNodes(TreeNode n) {\n            if (n == null) return 0;\n            \n            return 1 + countNodes(n.left) + countNodes(n.right);\n        }\n\n\nDFS in-order recursive:\n- time complexity: O(N)\n\n        // better keep these two variables in a wrapper class\n        private static int number = 0;\n        private static int count = 0;\n\n        public int kthSmallest(TreeNode root, int k) {\n            count = k;\n            helper(root);\n            return number;\n        }\n        \n        public void helper(TreeNode n) {\n            if (n.left != null) helper(n.left);\n            count--;\n            if (count == 0) {\n                number = n.val;\n                return;\n            }\n            if (n.right != null) helper(n.right);\n        }\n\nDFS in-order iterative:\n- time complexity: O(N) best\n\n      public int kthSmallest(TreeNode root, int k) {\n            Stack<TreeNode> st = new Stack<>();\n            \n            while (root != null) {\n                st.push(root);\n                root = root.left;\n            }\n                \n            while (k != 0) {\n                TreeNode n = st.pop();\n                k--;\n                if (k == 0) return n.val;\n                TreeNode right = n.right;\n                while (right != null) {\n                    st.push(right);\n                    right = right.left;\n                }\n            }\n            \n            return -1; // never hit if k is valid\n      }\n\n(edited: 7/2017)\n**note: requirement has been changed a bit since last time I visited that the counting could be looked up frequently and BST itself could be altered (inserted/deleted) by multiple times, so that\'s the main reason that I stored them in an array.** \n```\nclass Solution(object):\n    def kthSmallest(self, root, k):\n        """\n        :type root: TreeNode\n        :type k: int\n        :rtype: int\n        """\n        count = []\n        self.helper(root, count)\n        return count[k-1]\n        \n    def helper(self, node, count):\n        if not node:\n            return\n        \n        self.helper(node.left, count)\n        count.append(node.val)\n        self.helper(node.right, count)\n```\n\nDFS recursive, stop early when meet kth\n\n```\ndef findNode(node, res):\n            if len(res) > 1:\n                return\n\n            if node.left:\n                findNode(node.left, res)\n\n            res[0] -= 1\n            if res[0] == 0:\n                res.append(node.val)\n                return\n            \n            if node.right:\n                findNode(node.right, res)\n                \n        res = [k]\n        findNode(root, res)\n        return res[1]\n```\n\n\nThanks again!
['Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'Java']