Note
중위 순회로 오름차순을 만들고 k개만 채운 뒤 k번째(1-indexed) 값을 반환하는 코드 구조를 설명합니다.
문제 링크
문제 요약
- 입력: BST의
root, 정수k(1 ≤ k ≤ n) - 출력: 노드 값들 중 k번째로 작은 값 (1-indexed)
- BST: 이진 탐색 트리 (왼쪽 < 루트 < 오른쪽)
전체 코드
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
arr = []
def trav(node):
if len(arr) == k:
return
if node.left:
trav(node.left)
arr.append(node.val)
if node.right:
trav(node.right)
trav(root)
return arr[k - 1]코드 구조 설명
1. 값 수집용 리스트
arr = []- 중위 순회로 방문한 노드 값을 오름차순으로 쌓는 리스트
- 최대 k개만 채우고 나면 더 이상 순회하지 않음 (조기 종료)
2. 중위 순회 (trav)
def trav(node):
if len(arr) == k:
return
if node.left:
trav(node.left)
arr.append(node.val)
if node.right:
trav(node.right)| 단계 | 의미 |
|---|---|
len(arr) == k | 이미 k개 수집됨 → 더 볼 필요 없이 return |
trav(node.left) | 왼쪽 서브트리 먼저 (더 작은 값들) |
arr.append(node.val) | 현재 노드 값을 오름차순 순서로 추가 |
trav(node.right) | 오른쪽 서브트리 (더 큰 값들) |
순서가 왼쪽 → 현재 → 오른쪽이므로 BST에서 오름차순이 됩니다.
3. 조기 종료
if len(arr) == k:
return- 함수 시작 시에 체크하므로, 새 노드를 방문하기 전에 “이미 k개 찼는지” 확인
- k개가 찼으면 그 서브트리는 더 들어가지 않고 return
- 결과적으로 arr에는 정확히 k개의 값이 들어가고, arr[k-1] 이 k번째 작은 값(1-indexed)이 됨
4. 정답 반환
trav(root)
return arr[k - 1]trav(root)로 중위 순회를 하며 최대 k개까지arr에 채움- 1-indexed이므로 k번째 작은 값은 arr[k - 1]
데이터 흐름 요약
| 단계 | 역할 |
|---|---|
| arr | 중위 순회로 얻은 오름차순 값들 (최대 k개) |
| trav | 왼쪽 → 현재 노드 → 오른쪽 순서로 방문 |
| len(arr)==k | k개 채우면 더 이상 재귀하지 않고 return |
| arr[k-1] | k번째 작은 값 (1-indexed) |
예시: root = [5,3,6,2,4,null,null,1], k = 3
중위 순회 순서: 1 → 2 → 3 → 4 → 5 → 6
k=3이므로 1, 2, 3을 넣고 (필요하면 더 넣지만) 3번째 작은 값 = 3 → return 3
시간·공간 복잡도
- 시간: O(k) ~ O(n) — 조기 종료로 k개만 방문할 수 있고, 최악은 전체 노드 n
- 공간: O(h) 재귀 스택 (h = 트리 높이), arr는 O(k)
심화 이론
Note
**이진 탐색 트리(BST)에서는 중위 순회(Inorder) 가 오름차순이 됩니다. 따라서 ** 중위 순회에서 k번째로 방문한 노드가 k번째 작은 값입니다.
BST의 성질
이진 탐색 트리에서는:
- 왼쪽 서브트리의 모든 값 < 루트 < 오른쪽 서브트리의 모든 값
그래서 왼쪽 → 루트 → 오른쪽 순서로 방문하는 중위 순회(Inorder) 를 하면, 값이 작은 것부터 큰 것 순으로 나옵니다.
k번째 작은 값
- “k번째 작은 값” = 오름차순으로 나열했을 때 k번째 값
- 중위 순회가 오름차순이므로, 중위 순회에서 k번째로 방문한 노드의 값이 정답입니다.
방법:
- 중위 순회를 하면서 방문한 값을 순서대로 리스트에 넣거나,
- k개만 채우면 더 이상 순회하지 않고 그 리스트의 k번째(1-indexed) 를 반환
전체 중위 순회를 다 할 필요 없이, k개 채우면 조기 종료하면 됩니다.
중위 순회 순서 (Inorder)
왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리
재귀적으로:
node.left가 있으면 먼저 방문 (왼쪽 서브트리)- 현재 노드 처리 (값 수집 또는 카운트)
node.right가 있으면 방문 (오른쪽 서브트리)
이 순서로 방문하면 BST에서 값의 오름차순이 보장됩니다.
알고리즘 흐름
- 빈 리스트
arr(또는 카운터) 준비 - 중위 순회:
- 왼쪽 자식 있으면 먼저 재귀
- 현재 노드 값을
arr에 추가 - 이미 k개면 더 이상 재귀하지 않고 종료 (조기 종료)
- 오른쪽 자식 있으면 재귀
- arr[k-1] 반환 (1-indexed이므로)
예시: root = [3,1,4,null,2], k = 1
중위 순회: 왼쪽(1, 2) → 3 → 오른쪽(4) → 1, 2, 3, 4
- 1번째 작은 값 = 1 → 출력 1
시간·공간 복잡도
- 시간: O(k) ~ O(n) — 조기 종료 시 k개만 방문할 수도 있고, 최악은 전체 노드 n
- 공간: O(h) 재귀 스택 (h = 트리 높이), 값 저장 시 O(k) 또는 O(n)
Follow-up: 자주 수정·자주 조회할 때
BST에 삽입/삭제가 많고 k번째 작은 값을 자주 구해야 한다면:
- 각 노드에 왼쪽 서브트리의 노드 개수를 저장해 두고,
- k와 비교하면서 왼쪽/오른쪽으로 내려가면 O(h) 에 k번째 작은 값을 구할 수 있습니다.
- 삽입/삭제 시 해당 경로의 “왼쪽 개수”만 갱신하면 됩니다.