# 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 = 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
``````

• @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 = 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
``````

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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.