BST 검증과 중위 순회 속성
트리를 따라 전달하는 최솟값·최댓값 경계와 중위 순회 결과가 정렬된 수열인지 확인하는 방법으로 이진 트리가 BST인지 검증합니다.
BST 검증과 중위 순회 속성은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
BST 검증 문제
BST 검증(LeetCode #98)은 많은 지원자를 곤란하게 만드는 고전적인 면접 문제입니다. 단순한 방법은 각 노드의 값이 왼쪽 자식보다 크고 오른쪽 자식보다 작은지만 확인하는 것이지만, 이 지역 검사는 충분하지 않습니다. 부분 트리의 노드가 지역 규칙은 만족하면서도 전역 BST 속성을 위반할 수 있기 때문입니다. 올바른 해결책은 유효한 최솟값/최댓값 경계를 트리 아래로 전달하는 것입니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')최솟값/최댓값 경계 접근법
재귀 호출에 하한과 상한을 전달합니다. 각 노드에서 low < node.val < high인지 확인합니다. 왼쪽으로 재귀 호출할 때는 상한을 node.val로 갱신합니다(왼쪽 부분 트리의 값은 더 작아야 합니다). 오른쪽으로 재귀 호출할 때는 하한을 node.val로 갱신합니다(오른쪽 부분 트리의 값은 더 커야 합니다). low = -infinity와 high = +infinity로 시작합니다.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)중위 순회 검증
또 다른 검증 방법은 BST의 중위 순회 정렬 속성을 사용하는 것입니다. 중위 순회 순서를 수집한 뒤 그 순서가 엄격하게 증가하는지 확인합니다. 이 방법은 우아하고 추론하기 쉽습니다. 하지만 순서를 저장하기 위해 O(n)의 추가 공간이 필요합니다. 최적화된 버전에서는 순회 중 prev 포인터 하나만 사용하여 전체 순서를 저장하지 않고 각 쌍을 확인합니다.
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # False두 검증 접근법 비교
최솟값/최댓값 경계 접근법은 O(n) 시간과 O(h) 공간을 사용합니다(호출 스택에는 경계만 저장합니다). 중위 순회 prev 포인터 접근법도 O(n) 시간과 O(h) 공간을 사용합니다. 두 방법 모두 최적입니다. 최솟값/최댓값 접근법은 더 일반적이며 추가 제약이 있는 문제로 확장할 때도 깔끔하게 작동합니다. 면접에서는 두 방법을 모두 제시하고 장단점을 논의할 준비를 하십시오. 대안을 알고 있음을 보여 주는 것은 좋은 인상을 줍니다.
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')BST 복구: 서로 바뀐 두 노드
BST 복구(LeetCode #99)는 정확히 두 노드의 위치가 바뀐 BST를 복구하는 문제입니다. 올바른 순서의 BST를 중위 순회하면 정렬된 순서가 나옵니다. 두 노드의 위치가 바뀌면 prev.val > current.val인 한 번 또는 두 번의 위반이 발생합니다. 첫 번째 위반에서 처음 발견되는 노드와 마지막 위반에서 두 번째로 발견되는 노드가 위치가 바뀐 두 노드이므로, 두 노드의 값을 서로 바꿉니다.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)BST 중위 순회를 정렬 배열로 변환
BST를 정렬 배열로 변환하는 방법은 간단합니다. 중위 순회를 수행하여 값을 수집하면 됩니다. 이 O(n) 시간, O(n) 공간 연산은 정렬 배열 알고리즘(이진 탐색, 두 포인터)을 BST 데이터에 활용하는 빠른 방법입니다. ‘두 BST 병합’이나 ‘BST의 중앙값 찾기’ 같은 여러 단계로 이루어진 BST 문제를 풀기 위한 출발점으로 자주 사용됩니다.
def bst_to_sorted_array(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]두 BST 병합
두 BST를 병합하여 하나의 정렬 배열로 만들려면, 각 BST를 O(n)과 O(m)의 시간에 정렬 배열로 변환한 다음 병합 정렬의 병합 단계를 사용하여 두 정렬 배열을 O(n+m)의 시간에 병합합니다. 전체 시간 복잡도는 O(n+m)입니다. 결과를 균형 잡힌 BST로 만들어야 한다면 병합된 정렬 배열을 정렬 배열을 BST로 변환하는 알고리즘에 전달합니다. 이처럼 문제를 간단한 하위 문제로 분해하는 것이 명확하고 면접관이 이해하기 쉬운 해결책의 특징입니다.
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]BST 범위 내 노드 개수 세기
[low, high] 범위에 속하는 값을 가진 노드의 개수를 셉니다. 무차별 중위 순회는 O(n)입니다. BST의 특성을 활용하는 버전에서는 가지를 잘라냅니다. 현재 노드의 값이 low보다 작으면 왼쪽 부분 트리의 모든 값도 low보다 작으므로 왼쪽 부분 트리를 확인할 필요가 없습니다. 마찬가지로 현재 값이 high보다 크면 오른쪽 부분 트리를 잘라냅니다. 평균적인 경우의 시간 복잡도는 O(log n + k)이며, k는 조건에 일치하는 노드의 개수입니다.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7 + 10 + 15 = 32중복 값과 엄격/비엄격 BST
표준 BST 불변 조건은 엄격한 부등식을 사용합니다. 왼쪽 부분 트리의 값은 엄격하게 더 작고 오른쪽 부분 트리의 값은 엄격하게 더 커야 합니다. 일부 문제에서는 중복을 허용하여 중복 값을 왼쪽 부분 트리(왼쪽 값 <= 루트) 또는 오른쪽 부분 트리(루트 < 오른쪽 값)에 배치합니다. BST를 검증할 때는 문제 설명의 정의를 항상 확인하십시오. 최솟값/최댓값 경계 접근법은 경계 검사가 엄격한지 포함하는지 조정하여 두 변형을 모두 처리할 수 있습니다.
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')중위 순회: 만능 BST 도구
중위 순회는 BST 문제의 만능 도구입니다. BST 문제에서 정렬 순서, k번째 원소, 범위 질의 또는 순서의 속성을 묻는다면 중위 순회나 역중위 순회로 답을 구할 수 있는지 생각해 보십시오. 대부분의 BST 관련 문제는 정렬된 순서로 순회하면서 각 단계에서 무언가를 수행하는 것으로 단순화할 수 있습니다. 이러한 대응 관계를 빠르게 파악하는 능력은 중요한 면접 기술입니다.
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')BST에서 가장 가까운 값
주어진 목표값에 가장 가까운 값을 가진 노드를 찾습니다. BST의 정렬 순서를 활용하여 루트에서 시작하고, 지금까지 확인한 가장 가까운 값을 추적하면서 목표값을 향해 이동합니다(목표값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동합니다). 이 O(h) 접근법은 중위 순회보다 효율적이며, BST 속성을 효과적으로 활용하여 탐색 공간을 줄이는 방법을 보여 줍니다.
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인해 보십시오.
단원 요약
이 단원에서는 최솟값/최댓값 경계를 사용한 BST 검증(지역 검사 함정 회피), 검증을 위한 중위 순회 prev 포인터 대안, 그리고 범위 합, 가장 가까운 값, 병합 연산에 활용하는 만능 BST 도구로서의 중위 순회를 배웠습니다. 다음으로 BST의 중위 순회 특성을 사용하여 k번째로 작은 원소를 찾습니다.
자주 묻는 질문
“BST 검증과 중위 순회 속성” 강의는 무료인가요?
네 — “BST 검증과 중위 순회 속성” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“BST 검증과 중위 순회 속성”에서 뭘 배우나요?
트리를 따라 전달하는 최솟값·최댓값 경계와 중위 순회 결과가 정렬된 수열인지 확인하는 방법으로 이진 트리가 BST인지 검증합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“BST 검증과 중위 순회 속성” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- BST 삽입과 검색
- BST 삭제: 세 가지 경우
- BST 검증과 중위 순회 속성
- k번째 최솟값, 구간 합, BST를 정렬 배열로 변환