[LeetCode] 230. Kth Smallest Element in a BST

Problem

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 <= 10^4
• 0 <= Node.val <= 10^4

---

Solution

/**
 * 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) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        int cnt = 0;
        while (k != cnt) {
            TreeNode cur = stack.pop();
            cnt++;
            if (k == cnt) return cur.val;
            TreeNode right = cur.right;
            while (right != null) {
                stack.push(right);
                right = right.left;
            }
        }
        return -1;
    }
}

Explanation

• 문제에서 이진 검색 트리를 제시하고 있지만 이진 검색 트리에 대한 정보가 제시되어 있지는 않다. 문제를 풀기 위한 핵심이 되는 이진 검색 트리의 특성은 다음과 같다. ```java
• 각 노드의 값은 모두 유일하다.
• 부모 노드의 값은 왼쪽 자식노드 보다 크며, 오른쪽 자식 노드보다 작다. ```
• 위의 정보를 종합하면, 노드의 값 중 가장 작은 값은 이진 검색트리의 최하단부 가장 좌측 노드에 존재하고, 가장 큰 값은 최하단 부의 가장 우측 노드에 존재한다.
• k번째 크기인 노드의 값을 찾기 위해 이진 검색 트리의 최하단부 가장 좌측 노드부터 탐색하도록 한다.
• 최하단부 가장 좌측 노드를 탐색하기 위해 자료구조 Stack를 선언하고 지나왔던 노드들을 담고, while반복문을 통해 내려간다.

  Stack<TreeNode> stack = new Stack<>();
  while (root != null) {
    stack.push(root);
    root = root.left;
  }
  

• 우측 자식 노드들도 탐색할 수 있도록 while반복문을 중첩하여 작성한다.

  while (!stack.isEmpty()) {
    TreeNode cur = stack.pop();
    TreeNode right = cur.right;
    while (right != null) {
        stack.push(right);
        right = right.left;
    }
  }
  

• 노드 탐색 과정에서 카운트를 하여 k번째 크기인 노드를 발견하면 해당 노드의 값을 반환하도록 변수 cnt를 선언하고, if조건문을 작성한다. 파라미터 k의 값을 줄이는 방법도 있지만 파라미터를 그대로 두고 싶어서 변수 cnt를 선언했다.
• while반복문 내에서 값이 반환되지만 while반복문 밖에 return문이 없으면 제출이 되지 않아서 임의의 값인 -1을 반환하도록 하였다.

  int cnt = 0;
  while (k != cnt) {
    TreeNode cur = stack.pop();
    cnt++;
    if (k == cnt) return cur.val;
    TreeNode right = cur.right;
    while (right != null) {
        stack.push(right);
        right = right.left;
    }
  }
  return -1;