230. Kth Smallest Element in a BST

---

문제 분석

이진 검색 트리의 루트와 정수 k가 주어지면 트리에 있는 모든 노드 값 중 k번째로 작은 값(1-인덱스)을 반환합니다.

---

풀이 과정

이진 트리는 값(node)을 추가할 때 node 를 기준으로 값이 크다면 left 작다면 right 에 추가한다.
node 는 최대 2개의 자식 node 를 가질 수 있다.

두번째 예제로 [5, 3, 6, 2, 4, null, null, 1], k = 3 이 주어진다면,

• 5 는 root node 가 된다.
• 3 은 root node(5) 보다 작기 때문에 left
• 6 은 root node(5) 보다 크기 때문에 right
• 2 는 root node(5) 보다 작기 때문에 left
  • 2 는 3 보다 작기 때문에 left
• 4 는 root node(5) 보다 작기 때문에 left
  • 4 는 3 보다 크기 때문에 right
• 다음 2개의 null 은 6 은 리프 노드라고 알려준다.
• 1 은 root node(5) 보다 작기 때문에 left
  • 1 는 3 보다 작기 때문에 left
    - 1 은 2 보다 작기 때문에 left
    
• (완성된 구조)

이진 트리에서 몇 번째로 작은가?를 찾기 위해서는 우선 가장 작은 값을 찾아야한다.
가장 작은(left) 노드를 탐색하고 count 를 체크해준다.
재귀 함수를 빠져나오면서 count 를 올려주고,
count 와 몇 번째 가 같다면 해당 val 를 리턴하며 종료한다.

---

나의 생각

이진 트리의 특성을 이용한 재귀 함수의 베이스 조건 과 탐색 순서를 잘 고려한다면 쉽게 접근할 수 있다.
가장 작은 값을 우선적으로 찾는 것을 목표로 하고, 해당 값을 찾으면 count 를 올려주었다.
count 가 몇 번째 와 같은지 조건문으로 판단해주고, 이후 작은 값인 right 를 탐색해주었다.

재귀 함수의 로직 순서를 잘 고려하자!

---

코드

class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return result;
    }

    private void search(TreeNode node, int k) {
        if (node == null) return;

        search(node.left, k);
        count++;
        
        if(count == k) {
            result = node.val;
            return;
        }

        search(node.right, k);
    }

}