Python recursive solution (averaged time: O(lg(n)+k) ).
    \n    # averaged time complexity: log(n) + k\n    def kthSmallest(self, root, k):\n        self.k = k\n        self.res = 0\n        self.helper(root)\n    
        \n    # averaged time complexity: log(n) + k\n    def kthSmallest(self, root, k):\n        self.k = k\n        self.res = 0\n        self.helper(root)\n        return self.res\n        \n    def helper(self, root):\n        if root:\n            self.helper(root.left)\n            self.k -= 1\n            if self.k == 0:\n                self.res = root.val\n                return \n            self.helper(root.right)
['Recursion', 'Python']