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번째 작은 값을 구할 수 있습니다.
- 삽입/삭제 시 해당 경로의 “왼쪽 개수”만 갱신하면 됩니다.