# Python solution with detailed explanation

• Solution

Kth Smallest Element in a BST https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Inorder Traversal

1. You can do an inorder traversal using recursion or iteration and return the result in O(hleft + k). hleft is required to traverse to extreme left, from there it is O(k). The worst case complexity will be O(2N) or N. For a balanced tree, it should be O(lgN + k).
``````class Solution(object):
def inorder(self, root):
if root == None:
return
self.inorder(root.left)
self.k = self.k - 1
if self.k == 0:
self.ksmall = root.val
return
self.inorder(root.right)
return

def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.k = k
self.ksmall = None
self.inorder(root)
return self.ksmall
``````

Counting Elements Solution

• The other solution is to count the number of nodes on the left. Then decide whether the root is the kthsmallest or to go to the left or to go to the right. For a tree which is a linked list on the left side and k is 1, we have a N^2 algorithm. For a balanced tree, we have a N/2 + N/4 + ... = O(N).
``````class Solution(object):
def count(self, root):
if root == None:
return 0
return 1 + self.count(root.left) + self.count(root.right)

def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
less_than = self.count(root.left)
if k == less_than+1:
return root.val
elif k <= less_than:
return self.kthSmallest(root.left, k)
else:
return self.kthSmallest(root.right, k-1-less_than)
``````

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