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

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?

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

``````class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int cnt = 0;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
++cnt;
if (cnt == k) return p->val;
p = p->right;
}
return 0;
}
};
``````

``````class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
return kthSmallestDFS(root, k);
}
int kthSmallestDFS(TreeNode* root, int &k) {
if (!root) return -1;
int val = kthSmallestDFS(root->left, k);
if (k == 0) return val;
if (--k == 0) return root->val;
return kthSmallestDFS(root->right, k);
}
};
``````

``````class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int cnt = count(root->left);
if (k <= cnt) {
return kthSmallest(root->left, k);
} else if (k > cnt + 1) {
return kthSmallest(root->right, k - cnt - 1);
}
return root->val;
}
int count(TreeNode* node) {
if (!node) return 0;
return 1 + count(node->left) + count(node->right);
}
};
``````

``````// Follow up
class Solution {
public:
struct MyTreeNode {
int val;
int count;
MyTreeNode *left;
MyTreeNode *right;
MyTreeNode(int x) : val(x), count(1), left(NULL), right(NULL) {}
};

MyTreeNode* build(TreeNode* root) {
if (!root) return NULL;
MyTreeNode *node = new MyTreeNode(root->val);
node->left = build(root->left);
node->right = build(root->right);
if (node->left) node->count += node->left->count;
if (node->right) node->count += node->right->count;
return node;
}

int kthSmallest(TreeNode* root, int k) {
MyTreeNode *node = build(root);
return helper(node, k);
}

int helper(MyTreeNode* node, int k) {
if (node->left) {
int cnt = node->left->count;
if (k <= cnt) {
return helper(node->left, k);
} else if (k > cnt + 1) {
return helper(node->right, k - 1 - cnt);
}
return node->val;
} else {
if (k == 1) return node->val;
return helper(node->right, k - 1);
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/230

Binary Tree Inorder Traversal

Second Minimum Node In a Binary Tree

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

https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63659/what-if-you-could-modify-the-bst-nodes-structure

https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63660/3-ways-implemented-in-JAVA-(Python)%3A-Binary-Search-in-order-iterative-and-recursive

https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63743/Java-divide-and-conquer-solution-considering-augmenting-tree-structure-for-the-follow-up

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation