solution 1

/**
 * 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 arrOfTree = convertToArray(root);

    // k는 1부터 시작하기 때문에 -1 처리를 해준다.
    // O(n)
    return arrOfTree[k - 1];
};

function convertToArray(root, result=[]){
    if(!root){
        return;
    }

    convertToArray(root.left, result);
    result.push(root.val);
    convertToArray(root.right, result);

    return result;
}

BST를 정렬된 배열의 형태로 전환한 뒤, k 번째 원소를 얻는 방법이다.
그러나, 배열을 만든 뒤, k 번째 원소를 탐색하기 때문에 시간 복잡도가 크다.
아예 트리 구조에서 마무리를 지어버리는 방법을 고민해보자.

solution 2

/**
 * 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) {
    // BST의 가장 왼쪽이 가장 작은 값
    // 그의 부모가 2번째로 작은 값
    // 그의 부모가 3번째로 작은 값
    // ...

    let count = 0;
    let result;

    function recursive (node){
        if(!node){
            return;
        }

        recursive(node.left);

        count++;

        if(count === k){
            result = node.val;
        }

        recursive(node.right);
    }
    
    recursive(root);

    return result;
};

이번에는 배열로 변환하지 않고 트리 내에서 재귀를 통해 해결하는 방법을 사용했다.

BST의 특성 상 가장 왼쪽이 첫 번째로 작은 값이고,
그의 부모가 2번째로 작은 값,
그의 부모의 오른쪽이 3번째로 작은 값, ...
이런 식으로 반복되며 나아가기 때문에,
재귀를 통해 가장 아래에서부터 카운트를 진행해주면 k 번째 작은 값이라는 것을 빠르게 알 수 있다.

recursive()는 왼쪽 -> 본인 -> 오른쪽 순서로 순회를 하는데,
이를 활용해서 count를 증가시키도록 했다.
재귀 특성 상 가장 마지막에 호출된 함수부터 연산이 진행되는 것을 활용한 것이다.

이렇게 하면 가장 왼쪽 아래 노드부터 시작해서, 그의 부모, 오른쪽 노드,...
이런 식으로 되돌아오면서 count를 증가시키기 때문에 몇 번째로 작은 값인지를 알 수 있다.

다른 분들도 solution 1, solution 2의 방법을 사용하시는 것으로 보인다.