# 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.

Note:  You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

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?

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, int &k, int &res)
{
if(!root) return ;
dfs(root->left, k, res);
k--;
if(!k)
{
res = root->val;
return ;
}
dfs(root->right, k, res);
}
int kthSmallest(TreeNode* root, int k) {
int res;
dfs(root, k, res);
return res;
}
};```

0 条评论

• ### Leetcode 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a h...

• ### Leetcode 144 Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. For e...

• ### Leetcode 145 Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values. For ...

• ### Leetcode 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a h...

• ### Leetcode 145 Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values. For ...

• ### Leetcode 144 Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. For e...

• ### 【leetcode刷题】T130-二叉搜索树中第K小的元素

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

• ### 算法篇：树之倒数k个节点

这类题目的核心思想是，利用二叉树的中序遍历是从小到大的，将其转变成数组，然后对这个有序数组进行取值操作就可以了。

• ### 算法篇：树之树的层次遍历

树的层次遍历是树的基本操作之一，包括二叉树的层次遍历，多叉树的层次遍历，以及二叉树层次遍历的变形题目，层次遍历+每一层的节点的翻转等操作。