# 0230. 二叉搜索树中第 K 小的元素
### 题目地址(230. 二叉搜索树中第 K 小的元素)
### 题目描述
```
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
```
### 前置知识
* 中序遍历
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
解法一：
由于‘中序遍历一个二叉查找树（BST）的结果是一个有序数组’ ，因此我们只需要在遍历到第 k 个，返回当前元素即可。 中序遍历相关思路请查看[binary-tree-traversal](/leetcode-solution/thinkings/binary-tree-traversal.md)
解法二：
联想到二叉搜索树的性质，root 大于左子树，小于右子树，如果左子树的节点数目等于 K-1，那么 root 就是结果，否则如果左子树节点数目小于 K-1，那么结果必然在右子树，否则就在左子树。 因此在搜索的时候同时返回节点数目，跟 K 做对比，就能得出结果了。
### 关键点解析
* 中序遍历
### 代码
解法一：
JavaScript Code:
```js
/*
* @lc app=leetcode id=230 lang=javascript
*
* [230] Kth Smallest Element in a BST
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
const stack = [root];
let cur = root;
let i = 0;
function insertAllLefts(cur) {
while (cur && cur.left) {
const l = cur.left;
stack.push(l);
cur = l;
}
}
insertAllLefts(cur);
while ((cur = stack.pop())) {
i++;
if (i === k) return cur.val;
const r = cur.right;
if (r) {
stack.push(r);
insertAllLefts(r);
}
}
return -1;
};
```
Java Code:
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
private int count = 1;
private int res;
public int KthSmallest (TreeNode root, int k) {
inorder(root, k);
return res;
}
public void inorder (TreeNode root, int k) {
if (root == null) return;
inorder(root.left, k);
if (count++ == k) {
res = root.val;
return;
}
inorder(root.right, k);
}
```
解法二：
JavaScript Code:
```js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
function nodeCount(node) {
if (node === null) return 0;
const l = nodeCount(node.left);
const r = nodeCount(node.right);
return 1 + l + r;
}
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
const c = nodeCount(root.left);
if (c === k - 1) return root.val;
else if (c < k - 1) return kthSmallest(root.right, k - c - 1);
return kthSmallest(root.left, k);
};
```
**复杂度分析**
* 时间复杂度：$O(n^2)$，其中 n 为树的节点总数。
* 空间复杂度：$O(h)$ ，其中 h 为树的高度。
### 扩展
这道题有一个 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?`
建议大家思考一下。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/230.kth-smallest-element-in-a-bst.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.