Kth smallest element in a BST#

Levels: level-3

Data structures: tree

Algorithms: binary-search

Practice Link#

LeetCode

Description#

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Examples#

text

1Input: root = [3,1,4,null,2], k = 1
2   3
3  / \
4 1   4
5  \
6   2
7Output: 1

text

1Input: root = [5,3,6,2,4,null,null,1], k = 3
2       5
3      / \
4     3   6
5    / \
6   2   4
7  /
8 1
9Output: 3

Follow up#

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?
How would you optimize the kthSmallest routine?

Python Solution#

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution(object):
 9    def kthSmallestRecursive(self, root, k):
10        """
11        :type root: TreeNode
12        :type k: int
13        :rtype: int
14        """
15        def inorder(r):
16            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
17
18        return inorder(root)[k - 1]
19
20    def kthSmallestIterative(self, root, k):
21        """
22        :type root: TreeNode
23        :type k: int
24        :rtype: int
25        """
26        stack = []
27
28        while True:
29            while root:
30                stack.append(root)
31                root = root.left
32            root = stack.pop()
33            k -= 1
34            if not k:
35                return root.val
36            root = root.right