[Binary Search Tree] Kth Smallest Element in a BST

1. 문제

LeetCode - Kth Smallest Element in a BST

• 이진 탐색 트리의 루트 노드와 정수 k가 주어졌을 때
• 모든 노드의 값 중에서 k번째로 작은 값을 반환하는 문제

2. 접근법

• 이진 탐색 트리는 중위 순회를 했을 때 오름차순 정렬 순서로 탐색이 가능하다는 사실을 이용
• k번째 작은 값을 반환하면 되기 때문에 values에 노드의 값을 순서대로 채워준 뒤, k - 1번 인덱스의 값을 반환 -> 성공!
• 별도의 자료구조를 활용하지 않고 멤버 변수 count와 result를 활용하는 방식으로 개선

3. 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // 1. 모든 노드의 값을 담아줄 values
        List<Integer> values = new ArrayList<>();

        // 2. 중위 순회를 통해 values에 값을 순서대로 채우기
        inOrderSearch(root, values);

        // 3. values의 k - 1번째 값 리턴(인덱스는 0부터 시작하므로)
        return values.get(k - 1);
    }

    // 중위 순회
    private void inOrderSearch(TreeNode node, List<Integer> values) {
        if (node.left != null) inOrderSearch(node.left, values);
        values.add(node.val);
        if (node.right != null) inOrderSearch(node.right, values);
    }

}

4. 성능

- Runtime : 1ms -> 0ms

- Memory : 43.77mb

5. 개선

class Solution {

    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        // 중위 순회를 하면서 count가 k가 되었을 때 노드 값을 반환
        inOrderSearch(root, k);

        return result;
    }

    // 중위 순회를 하면서 count를 늘려주고
    // k번째 작은 값을 만났을 때 result에 노드의 값을 담아준다.
    private void inOrderSearch(TreeNode node, int k) {
        if (node.left != null) inOrderSearch(node.left , k);
        count++;
        if (count == k) result = node.val;
        if (node.right != null) inOrderSearch(node.right, k);
    }

}