# Leetcode: Kth Smallest Element in a BST

Kth Smallest Element in a BST

Similar Problems:

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/kth-smallest-element-in-a-bst
## Basic Ideas: In-order trasversal
## Complexity: O(k), Space O(k)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
(quota, val) = self.inorderVisit(root, k)
# quota must be 0, since k is valid.
return val

def inorderVisit(self, root, k):
if k == 0: return (0, None)
if root is None: return (k, None)

quota, val = k, root.val
if root.left:
(quota, val) = self.inorderVisit(root.left, quota)
if quota == 0: return (0, val)
if quota == 1: return (0, root.val)
quota -= 1
if root.right:
(quota, val) = self.inorderVisit(root.right, quota)
return (quota, val)
```

Share It, If You Like It.