# 230. Kth Smallest Element in a BST

## 題目敘述

Given the `root` of a binary search tree, and an integer `k`, return the `k**th` smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the tree is `n`.
• `1 <= k <= n <= 10**4`
• `0 <= Node.val <= 10**4`

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Hint 1:

Try to utilize the property of a BST.

Hint 2:

Try in-order traversal.

Hint 3:

What if you could modify the BST node's structure?

Hint 4:

The optimal runtime complexity is O(height of BST).

## 解法解析

### 解法範例

#### Go

##### Iteration
``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
stack := []*TreeNode{}
cur := root

for k >= 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}

cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
k--
if k == 0 {
return cur.Val
}
cur = cur.Right
}

return cur.Val
}
``````
##### Recursion
``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
cur := 0
val := 0
dfs(root, k, &cur, &val)
return val

}

func dfs(node *TreeNode, k int, cur, val *int) {
if node == nil {
return
}
dfs(node.Left, k, cur, val)

*cur = *cur + 1
if *cur == k {
*val = node.Val
}
dfs(node.Right, k, cur, val)
}
``````

#### JavaScript

##### Iteration
``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
const stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
k--;
if (!k) {
return cur.val;
}
cur = cur.right;
}
};
``````
##### Recursion
``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
function inorder(root) {
if (!root) return;
inorder(root.left);
if (--k === 0) {
return;
}
inorder(root.right);
}
inorder(root);
};
``````

#### Kotlin

``````
``````

#### PHP

``````
``````

#### Python

##### Iteration
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []

while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
``````
##### Recursion
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
def inorder(r):
return inorder(r.left) + [r.val] + inorder(r.right) if r else []

return inorder(root)[k - 1]
``````

#### Rust

``````
``````

#### Swift

``````
``````