# LeetCode: 230. Kth Smallest Element in a BST

## 题目¶

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

Example 1:

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

Example 2:

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

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?

Constraints:

• The number of elements of the BST is between 1 to 10^4.
• You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

## 解法¶

### 中序遍历生成数组，找出数组的第 k 个元素¶

```def inorder(root):
if root is None:
return
inorder(root.left)

# print(root)

inorder(root.right)
```

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def kthSmallest(self, root, k):
self.node_vals = []
self.inorder(root)
return self.node_vals[k-1]

def inorder(self, root):
if root is None:
return
self.inorder(root.left)

self.node_vals.append(root.val)

self.inorder(root.right)
```

### 中序遍历直接找到相应的元素¶

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def kthSmallest(self, root, k):
self.number = 0
self.node_val = None
self.inorder(root, k)
return self.node_val

def inorder(self, root, k):
if root is None:
return

self.inorder(root.left, k)

self.number += 1
if self.number == k:
self.node_val = root.val
return

self.inorder(root.right, k)
```