[LeetCode] DFS - 230. Kth Smallest Element in a BST

문제

Given the root of a binary search tree, and an integer k, return the kth 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 <= 104
• 0 <= Node.val <= 104

---

코드

var kthSmallest = function(root, k) {
    let result;
    let n = 0;
    
    // Binary Search Tree이기 때문에 크고 작은 것으로 구분돼있음
    // 작은건 보통 왼쪽에 있으므로
    // DFS를 선택
    // 따라서 DFS로 내려가면서 'here'에 k번째 방문 때의 값이 답임
    function dfs(num) {
        if(!num) return ;
        dfs(num.left)
        if(n++ < k) result = num.val // here
        dfs(num.right)
    }
    
    dfs(root)
    
    return result
}