## Question

>[Leetcode.230 Kth Smallest Element In a Bst
](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * 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}
 */

/* Time: O(n),  Space: O(n) */
var kthSmallest = function(root, k) {
    // Use the in-order traversal to convert the tree to the array
    const array = []
    traversal(root, array);
    return array[k-1];
};

function traversal(node, array){
    if(!node) return
    traversal(node.left, array);
    array.push(node.val);
    traversal(node.right, array);
}

:::

<hr/>

### Sol
:::spoiler Code

var kthSmallest = function(root, k) {
    var data = [];
    let stop = false;
    const traverse = (node)=>{
        if(stop) return;
        if (node.left)
            traverse(node.left);
        if(k === data.length){
            stop = true;
        }
        data.push(node.val);
        if (node.right)
            traverse(node.right);
				
    }
    traverse(root);
    return data[k-1]
};

:::

<hr/>

### 東

In Order Traversal allow us to traverse node from smallest to largest


:::spoiler Code

// Time O(n) | Space O(h)
// n is the number of nodes
// h is the height of the tree
var kthSmallest = function(root, k) {
    let currIdx = 0;
    let ans = null;
    (function inOrderTraversal(node){        
        if(!node || ans !== null) return;
        inOrderTraversal(node.left);
        if(++currIdx === k) ans = node.val;
        inOrderTraversal(node.right);
    })(root);
    return ans;
};

:::

<hr/>

### Jessie

:::spoiler Code

var kthSmallest = function (root, k) {

  //  解法1: 👎👎 暴力解 （遍歷出所有 node 之後由小到大排序，找到 index = k-1）
  let nodeList = [];
  const queue = [];

  queue.push(root);

  while (queue.length > 0) {
    const node = queue.pop();
    nodeList.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  nodeList = nodeList.sort((a, b) => a - b);
  return nodeList[k - 1];

  //  解法2: BST 特性 in order 遍歷
  
};

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

# 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:
        # idea 1: dfs, in order traversal
        # time O(N)
        # space O(N)
        
        count = 0  # 看過幾個 node
        result = None
        
        def dfs(r):
            nonlocal count, result
            if result is not None or not r:  # 如果找到結果，就提前結束 dfs
                return
            if r.left: dfs(r.left)
            count += 1
            if count == k:
                result = r.val
                return  # 如果找到結果，就提前結束 dfs
            if r.right: dfs(r.right)
        
        dfs(root)
        return result

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::

<hr/>

## Related Question Discussion

[105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)