def kthSmallest(self, root, k):
mid = root
while True:
l = mid.left
r = mid.right
lCount = self.nodesCount(l)
rCount = self.nodesCount(r)
if lCount == k  1:
return mid.val
if lCount < k  1:
mid = r
k = k  lCount  1
else:
mid = l
def nodesCount(self, node):
if node is None:
return 0
stack = [node]
count = 1
while len(stack):
cur = stack.pop()
if cur.left:
stack.append(cur.left)
count += 1
if cur.right:
stack.append(cur.right)
count += 1
return count
Python BST solution


@mpan753 said in Python BST solution:
def kthSmallest(self, root, k):
mid = root
while True:
l = mid.left
r = mid.right
lCount = self.nodesCount(l)
rCount = self.nodesCount(r)
if lCount == k  1:
return mid.val
if lCount < k  1:
mid = r
k = k  lCount  1
else:
mid = ldef nodesCount(self, node): if node is None: return 0 stack = [node] count = 1 while len(stack): cur = stack.pop() if cur.left: stack.append(cur.left) count += 1 if cur.right: stack.append(cur.right) count += 1 return count
nice solution. I never thought of doing binary search using node count in a tree however this solution is just 30% better than other solutions. Whereas simple inorder traversal makes the solution 91% better.
class Solution(object): count = 0 result = None def kthSmallestUtil(self, root, k): if root is None: return if self.result is not None: return self.result self.kthSmallestUtil(root.left, k) self.count = self.count + 1 if (self.count == k): self.result = root.val return root.val self.kthSmallestUtil(root.right, k) def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ self.kthSmallestUtil(root, k) return self.result