Five solutions in Python: recursive, iterative in-order, binary-search
Five different ways.\n\nAccording to \nhttps://leetcode.com/discuss/43771/implemented-java-binary-search-order-iterative-recursive\nhttps://leetcode.com/discuss
Five different ways.\n\nAccording to \nhttps://leetcode.com/discuss/43771/implemented-java-binary-search-order-iterative-recursive\nhttps://leetcode.com/discuss/44731/pythonic-approach-with-generator\n\n    # Binary search iterative\n    class Solution(object):\n        def kthSmallest(self, root, k):\n            count = self.get_nodes(root.left)\n            while count + 1 != k:\n                if count + 1 < k:\n                    root = root.right\n                    k = k - count - 1\n                else:\n                    root = root.left\n                count = self.get_nodes(root.left)\n            return root.val\n    \n        def get_nodes(self, root):\n            if not root:\n                return 0\n            return 1 + self.get_nodes(root.left) + self.get_nodes(root.right)\n    \n    \n    # Binary search recursive\n    class Solution_2(object):\n        def kthSmallest(self, root, k):\n            count = self.get_nodes(root.left)\n            if count+1 < k:\n                return self.kthSmallest(root.right, k-count-1)\n            elif count+1 == k:\n                return root.val\n            else:\n                return self.kthSmallest(root.left, k)\n    \n        def get_nodes(self, root):\n            if not root:\n                return 0\n            return 1 + self.get_nodes(root.left) + self.get_nodes(root.right)\n    \n    \n    # DFS in-order iterative:\n    class Solution_3(object):\n        def kthSmallest(self, root, k):\n            node_stack = []\n            count, result = 0, 0\n            while root or node_stack:\n                if root:\n                    node_stack.append(root)\n                    root = root.left\n                else:\n                    if node_stack:\n                        root = node_stack.pop()\n                        result = root.val\n                        count += 1\n                        if count == k:\n                            return result\n                        root = root.right\n    \n            return -1   # never hit if k is valid\n    \n    \n    # DFS in-order recursive:\n    class Solution_4(object):\n        def kthSmallest(self, root, k):\n            self.k = k\n            self.num = 0\n            self.in_order(root)\n            return self.num\n    \n        def in_order(self, root):\n            if root.left:\n                self.in_order(root.left)\n            self.k -= 1\n            if self.k == 0:\n                self.num = root.val\n                return\n            if root.right:\n                self.in_order(root.right)\n    \n    \n    # DFS in-order recursive, Pythonic approach with generator:\n    class Solution_5(object):\n        def kthSmallest(self, root, k):\n            for val in self.in_order(root):\n                if k == 1:\n                    return val\n                else:\n                    k -= 1\n    \n        def in_order(self, root):\n            if root:\n                for val in self.in_order(root.left):\n                    yield val\n                yield root.val\n                for val in self.in_order(root.right):\n                    yield val
['Depth-First Search', 'Binary Tree', 'Python']