# [LeetCode] Kth Smallest Element in a BST 二叉搜索树中的第K小的元素

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.

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?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node's structure?
3. The optimal runtime complexity is O(height of BST).

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);
}
}
};```

Binary Tree Inorder Traversal

Second Minimum Node In a Binary Tree

https://discuss.leetcode.com/topic/17668/what-if-you-could-modify-the-bst-node-s-structure

https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-python-binary-search-in-order-iterative-recursive

https://discuss.leetcode.com/topic/32792/java-divide-and-conquer-solution-considering-augmenting-tree-structure-for-the-follow-up