[LeetCode] Kth Smallest Element in a BST - Javascript

Kth Smallest Element in a BST

[이진 탐색 트리, k번째로 작은 수 찾기]

제약 조건

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

Example

문제 접근 방식

주어지는 트리가 이진 탐색 트리이고, k가 주어지면 k 번째로 작은 노드를 반환하면 되기에,
중위 순회 방법으로 쉽게 풀 수 있다.

중위 순회는 노드의 가장 왼쪽 - 루트 - 오른쪽 순으로 순회를 하는데,
이진 트리 탐색이기에, 가장 작은 수는 왼쪽부터 있는 특성을 이용해 풀 수 있었다.
먼저 재귀 함수를 만들어 root를 받아 data가 존재하지 않으면 리턴하는 제어문을 작성한다.

이후 노드의 맨 왼쪽부터 접근이 가능하도록 recusive 함수를 재귀 호출한다.
data.left가 존재할 때까지 재귀 호출을 하고 이후 index를 1씩 증가하며,
k와 값이 같은지 비교하고 같을 때 현재 노드의 값을 smallest 변수에 값을 넣고 리턴한다.

이후 data.right도 재귀 호출해 반복하여 값을 찾는다.

 

접근 코드

/**
 * 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) {
   let index = 0;
   let smallest;
   const recursive = data => {
      if (!data) {
         return;
      }
      recursive(data.left);
      index++;
      if (index == k) {
         smallest = data.val;
         return;
      }
      recursive(data.right);
   };

   recursive(root);
   return smallest;
};