← 전체 회차
A-057● Day 572026.07.03mediumleetcode #230neetcode150

이진 검색 트리에서 k번째 작은 원소

#tree#depth-first-search#binary-search-tree#binary-tree
↗ leetcode #230 · kth-smallest-element-in-a-bst
01

문제

· problem
P.057

이진 검색 트리에서 k번째 작은 원소

↗ leetcode #230

이진 검색 트리의 루트와 정수 k가 주어질 때, 트리의 모든 노드 값 중에서 k번째로 작은 값(1-indexed)을 반환하세요.

제약
  • · 1 ≤ k ≤ n ≤ 10⁴
  • · 0 ≤ Node.val ≤ 10⁴
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,1,4,null,2]
1
1
example 2input → output
[5,3,6,2,4,null,null,1]
3
3
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    이 문제에서 '1-indexed'는 무엇을 의미합니까?
  • ☐
    BST에 중복된 값이 있을 수 있습니까?
  • ☐
    트리는 항상 유효한 BST입니까?
  • ☐
    솔루션이 트리 구조를 수정해야 합니까?
  • ☐
    우리는 k번째로 큰 원소를 찾아야 합니까?
  • ☐
    트리는 항상 완벽하게 균형잡혀 있습니까?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 스택 초기화
○
stack = []
○
stack = [root]
○
stack = {}
step 2· 반복 조건 설정
○
while stack or curr:
○
while curr:
○
while stack:
step 3· 왼쪽끝까지 탐색│ │ 중첩
○
curr = curr.left
○
curr = curr.right
○
while curr: k -= 1
step 4· 스택에서 노드 제거│ 중첩
○
curr = stack.pop()
○
curr = stack[0]
○
stack.pop()
step 5· k번째 원소 확인│ │ 중첩
○
if k == 0:
○
if k == 1:
○
if k < 0:
step 6· 오른쪽 부분트리 탐색│ 중첩
○
curr = curr.right
○
curr = curr.left
○
stack.append(curr.right)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.left = None
6
#         self.right = None
7
8
9
class Solution:
10
    def kthSmallest(self, root: TreeNode, k: int) -> int:
11
        stack = []
12
        curr = root
13
14
        while stack or curr:
15
            while curr:
16
                stack.append(curr)
17
                curr = curr.left
18
            curr = stack.pop()
19
            k -= 1
20
            if k == 0:
21
                return curr.val
22
            curr = curr.right
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,1,4,null,2]
1
→
1
case 2
[5,3,6,2,4,null,null,1]
3
→
3
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.