이미지 로딩 중...
AI Generated
2025. 11. 7. · 4 Views
BST 검증 알고리즘 완벽 가이드
이진 탐색 트리(BST)의 유효성을 검증하는 핵심 알고리즘을 실무 관점에서 깊이 있게 다룹니다. 범위 기반 검증부터 중위 순회 방식까지, 각 접근법의 장단점과 최적화 기법을 학습합니다.
목차
- BST 기본 검증 - 재귀적 범위 체크
- 중위 순회 기반 검증 - 정렬 순서 확인
- 반복적 중위 순회 - 스택 기반 검증
- Morris 순회 기반 검증 - O(1) 공간 복잡도
- 재귀 + 서브트리 정보 반환 - 최적화된 검증
- 범위 체크 최적화 - 정수 오버플로우 처리
- 배열 기반 빠른 검증 - 중위 순회 결과 비교
- 경계 조건 강화 - 중복 값 허용 BST
1. BST 기본 검증 - 재귀적 범위 체크
시작하며
여러분이 트리 기반 데이터 구조를 다루다가 갑자기 예상치 못한 검색 결과가 나오는 상황을 겪어본 적 있나요? 예를 들어, 정렬된 데이터를 빠르게 찾기 위해 BST를 구현했는데, 어떤 값은 제대로 찾아지고 어떤 값은 찾지 못하는 경우가 발생합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. BST의 속성이 깨진 트리는 O(log n)의 검색 성능을 보장하지 못하고, 최악의 경우 O(n)의 선형 탐색으로 퇴화됩니다.
특히 동적으로 노드를 삽입하거나 삭제하는 과정에서 BST 속성이 위반되는 경우가 많습니다. 바로 이럴 때 필요한 것이 BST 검증 알고리즘입니다.
트리가 올바른 BST 속성을 유지하고 있는지 확인하여, 데이터 무결성과 성능을 보장할 수 있습니다.
개요
간단히 말해서, 이 알고리즘은 각 노드가 허용된 값의 범위 내에 있는지 확인하는 재귀적 방법입니다. BST의 핵심 속성은 "왼쪽 서브트리의 모든 노드 < 현재 노드 < 오른쪽 서브트리의 모든 노드"입니다.
단순히 자식 노드와만 비교해서는 안 되며, 조상 노드들이 만든 범위 제약도 고려해야 합니다. 예를 들어, 루트가 10인 트리에서 오른쪽 서브트리에 5가 있다면, 직접 부모보다는 크더라도 BST 속성을 위반한 것입니다.
전통적인 방법에서는 각 노드마다 왼쪽, 오른쪽 자식만 체크했다면, 이제는 최소/최대 범위를 추적하며 전체 서브트리를 검증할 수 있습니다. 이 알고리즘의 핵심 특징은 (1) 각 노드에 대해 허용 가능한 값의 범위를 동적으로 업데이트하고, (2) 재귀적으로 서브트리를 검증하며, (3) 범위 위반 시 즉시 false를 반환한다는 것입니다.
이러한 특징들이 트리 전체의 무결성을 보장하고 조기 종료로 불필요한 연산을 줄입니다.
코드 예제
function isValidBST(root, min = -Infinity, max = Infinity) {
// 빈 노드는 유효한 BST
if (root === null) return true;
// 현재 노드가 범위를 벗어나면 유효하지 않음
if (root.val <= min || root.val >= max) return false;
// 왼쪽 서브트리: 최대값을 현재 노드로 제한
// 오른쪽 서브트리: 최소값을 현재 노드로 제한
return isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max);
}
설명
이것이 하는 일: 이 함수는 트리의 각 노드를 방문하면서, 해당 노드가 위치해야 할 값의 범위를 체크합니다. 루트에서 시작해 리프 노드까지 내려가면서 각 레벨에서 허용 범위를 점진적으로 좁혀갑니다.
첫 번째로, 베이스 케이스에서 null 노드를 만나면 true를 반환합니다. 빈 트리나 리프 노드의 자식은 항상 유효한 BST로 간주됩니다.
이는 재귀 종료 조건으로 작동하며, 트리의 끝에 도달했음을 의미합니다. 두 번째로, 현재 노드의 값이 허용 범위(min, max)를 벗어나는지 체크합니다.
여기서 주의할 점은 등호를 포함한다는 것입니다(<=, >=). BST는 중복 값을 허용하지 않기 때문에, 경계값과 같으면 안 됩니다.
범위를 벗어나면 즉시 false를 반환하여 불필요한 탐색을 중단합니다. 세 번째로, 재귀 호출에서 범위를 업데이트합니다.
왼쪽 자식으로 내려갈 때는 max를 현재 노드 값으로 설정하여 "이 값보다 작아야 함"을 표현하고, 오른쪽 자식으로 갈 때는 min을 현재 노드 값으로 설정하여 "이 값보다 커야 함"을 표현합니다. 두 서브트리 모두 유효해야 전체가 유효하므로 AND 연산자를 사용합니다.
여러분이 이 코드를 사용하면 트리의 모든 노드가 BST 속성을 만족하는지 확실하게 검증할 수 있습니다. 시간 복잡도는 O(n)으로 모든 노드를 한 번씩 방문하며, 공간 복잡도는 O(h)로 재귀 스택의 깊이(트리의 높이)에 비례합니다.
조기 종료 로직 덕분에 잘못된 트리를 빠르게 감지할 수 있습니다.
실전 팁
💡 초기 호출 시 min과 max를 -Infinity와 Infinity로 설정하여 루트 노드에 제약이 없음을 표현하세요. 이렇게 하면 정수 범위를 벗어나는 값도 안전하게 처리할 수 있습니다.
💡 등호 처리를 주의하세요. root.val <= min이 아닌 root.val < min으로 작성하면 중복 값을 허용하게 되어 BST 정의에 맞지 않습니다. 요구사항에 따라 중복 허용 여부를 결정하세요.
💡 큰 정수를 다룰 때는 Number.MIN_SAFE_INTEGER와 Number.MAX_SAFE_INTEGER를 사용하는 것이 더 안전합니다. Infinity는 비교 연산에서 예상치 못한 결과를 낼 수 있습니다.
💡 디버깅 시 각 노드에서 현재 범위를 로깅하면 어디서 속성이 깨지는지 쉽게 파악할 수 있습니다. 예: console.log(Node ${root.val}: range [${min}, ${max}])
💡 이 패턴은 다른 트리 검증 문제에도 응용 가능합니다. 예를 들어 AVL 트리의 균형 검증이나 힙 속성 검증에도 범위 기반 재귀를 활용할 수 있습니다.
2. 중위 순회 기반 검증 - 정렬 순서 확인
시작하며
여러분이 BST 검증 로직을 작성하면서 "더 직관적인 방법은 없을까?"라고 생각해본 적 있나요? 특히 BST의 가장 중요한 속성인 "중위 순회 시 오름차순"을 직접 활용하고 싶을 때가 있습니다.
이 방법은 실제로 많은 개발자들이 선호하는 접근법입니다. BST의 정의를 그대로 코드로 옮긴 것이기 때문에 이해하기 쉽고, 범위 관리의 복잡함 없이 이전 값과의 비교만으로 검증할 수 있습니다.
면접 상황에서도 이 방법을 설명하면 BST에 대한 깊은 이해를 보여줄 수 있습니다. 바로 이럴 때 필요한 것이 중위 순회 기반 검증입니다.
트리를 순회하면서 이전 노드 값과 비교하여 정렬 순서가 유지되는지 확인합니다.
개요
간단히 말해서, 이 알고리즘은 트리를 중위 순회(in-order traversal)하면서 방문하는 노드들이 오름차순을 유지하는지 검사하는 방법입니다. BST의 중요한 수학적 속성은 중위 순회 시 모든 노드가 정렬된 순서로 방문된다는 것입니다.
따라서 순회 중 이전 값보다 작거나 같은 값이 나타나면 BST 속성이 깨진 것입니다. 예를 들어, 순회 결과가 [2, 4, 6, 5, 8]이라면 6 다음에 5가 나왔으므로 유효하지 않은 BST입니다.
기존 범위 기반 검증은 각 노드마다 min/max를 관리해야 했다면, 이제는 단순히 이전 값(prev) 하나만 추적하면 됩니다. 이 알고리즘의 핵심 특징은 (1) BST의 수학적 속성을 직접 활용하여 검증하고, (2) 상태를 최소화하여 메모리 효율적이며, (3) 순회 패턴을 이해하면 구현과 디버깅이 쉽다는 것입니다.
이러한 특징들이 코드의 가독성과 유지보수성을 높입니다.
코드 예제
function isValidBST(root) {
let prev = -Infinity;
function inorder(node) {
// 빈 노드는 유효
if (node === null) return true;
// 왼쪽 서브트리 먼저 검증
if (!inorder(node.left)) return false;
// 현재 노드가 이전 값보다 작거나 같으면 무효
if (node.val <= prev) return false;
prev = node.val;
// 오른쪽 서브트리 검증
return inorder(node.right);
}
return inorder(root);
}
설명
이것이 하는 일: 이 함수는 트리를 중위 순회(왼쪽 → 현재 → 오른쪽) 순서로 방문하면서, 각 노드의 값이 이전에 방문한 노드의 값보다 큰지 확인합니다. 클로저를 활용하여 prev 변수에 마지막으로 방문한 노드의 값을 저장합니다.
첫 번째로, 외부 함수에서 prev를 -Infinity로 초기화합니다. 이는 첫 번째로 방문하는 노드(가장 왼쪽 노드)가 어떤 값이든 prev보다 크도록 보장합니다.
내부 함수 inorder가 이 변수에 접근할 수 있도록 클로저를 형성합니다. 두 번째로, 중위 순회의 왼쪽 단계에서 왼쪽 서브트리를 먼저 재귀적으로 검증합니다.
왼쪽 서브트리가 유효하지 않으면 즉시 false를 반환하여 나머지 검사를 생략합니다. 이는 중위 순회의 핵심 패턴으로, 가장 작은 값부터 순서대로 처리하기 위함입니다.
세 번째로, 현재 노드를 처리합니다. 현재 노드의 값이 이전 값 이하라면 정렬 순서가 깨진 것이므로 false를 반환합니다.
그렇지 않으면 prev를 현재 값으로 업데이트하여 다음 노드 검증에 사용합니다. 마지막으로 오른쪽 서브트리를 검증하고 그 결과를 반환합니다.
여러분이 이 코드를 사용하면 BST의 본질적인 속성을 직접 활용하여 검증할 수 있습니다. 시간 복잡도는 O(n)으로 모든 노드를 한 번씩 방문하며, 공간 복잡도는 O(h)로 재귀 스택의 깊이에 비례합니다.
범위 기반 방법과 성능은 동일하지만, 코드가 더 직관적이고 BST의 정의에 충실합니다.
실전 팁
💡 prev를 전역 변수 대신 클로저로 관리하면 함수를 여러 번 호출해도 안전합니다. 전역 변수를 사용하면 동시에 여러 트리를 검증할 때 값이 섞일 수 있습니다.
💡 반복적(iterative) 중위 순회로 구현하면 스택 오버플로우 위험을 줄일 수 있습니다. 명시적 스택을 사용하여 깊은 트리도 안전하게 처리할 수 있습니다.
💡 실무에서는 순회 중 발견한 모든 위반 사항을 로깅하면 디버깅에 도움이 됩니다. 예: if (node.val <= prev) console.error(Violation at node ${node.val}, prev was ${prev})
💡 중복 값을 허용하는 변형 BST라면 조건을 node.val < prev로 변경하세요. 하지만 일반적으로 BST는 중복을 허용하지 않습니다.
💡 이 패턴은 "정렬 검증"이 필요한 모든 상황에 응용 가능합니다. 배열이 정렬되었는지 확인하거나, 연결 리스트의 정렬 여부를 체크하는 데도 같은 논리를 사용할 수 있습니다.
3. 반복적 중위 순회 - 스택 기반 검증
시작하며
여러분이 매우 깊은 트리를 다루면서 재귀 호출 때문에 스택 오버플로우 에러를 만난 적 있나요? 특히 불균형한 트리에서는 재귀 깊이가 수천, 수만 레벨에 달할 수 있어 프로그램이 비정상 종료될 수 있습니다.
이런 문제는 실제 프로덕션 환경에서 심각한 장애로 이어질 수 있습니다. 예를 들어, 사용자가 계속 증가하는 데이터로 편향된 트리를 만들었다면, 검증 함수가 크래시를 일으켜 서비스 중단으로 이어질 수 있습니다.
재귀의 우아함은 좋지만, 안정성이 더 중요한 경우가 많습니다. 바로 이럴 때 필요한 것이 반복적 중위 순회입니다.
명시적 스택을 사용하여 재귀를 제거하고, 메모리를 직접 제어하여 깊은 트리도 안전하게 처리합니다.
개요
간단히 말해서, 이 알고리즘은 명시적 스택 자료구조를 사용하여 중위 순회를 구현하고, 재귀 없이 BST를 검증하는 방법입니다. 재귀 함수는 내부적으로 콜 스택을 사용하는데, 이를 우리가 직접 관리하는 스택으로 대체합니다.
이렇게 하면 스택 크기를 제어할 수 있고, 깊이 제한에 걸리지 않습니다. 예를 들어, 10,000개 노드가 일렬로 연결된 편향 트리도 안전하게 검증할 수 있습니다.
기존 재귀 방법이 함수 호출로 상태를 관리했다면, 이제는 while 루프와 스택으로 동일한 동작을 구현합니다. 이 알고리즘의 핵심 특징은 (1) 스택 오버플로우 위험이 없어 안전하고, (2) 메모리 사용량을 명시적으로 제어할 수 있으며, (3) 디버깅 시 스택 상태를 직접 확인할 수 있다는 것입니다.
이러한 특징들이 프로덕션 환경에서의 안정성과 유지보수성을 크게 향상시킵니다.
코드 예제
function isValidBST(root) {
const stack = [];
let current = root;
let prev = -Infinity;
while (current !== null || stack.length > 0) {
// 가장 왼쪽 노드까지 이동
while (current !== null) {
stack.push(current);
current = current.left;
}
// 스택에서 노드를 꺼내 처리
current = stack.pop();
// 정렬 순서 검증
if (current.val <= prev) return false;
prev = current.val;
// 오른쪽 서브트리로 이동
current = current.right;
}
return true;
}
설명
이것이 하는 일: 이 함수는 while 루프와 배열 스택을 사용하여 트리를 중위 순회하며, 각 노드가 이전 노드보다 큰지 확인합니다. 재귀 대신 명시적 제어 흐름을 사용하여 깊이 제한 없이 트리를 탐색합니다.
첫 번째로, 초기화 단계에서 빈 스택과 current 포인터를 루트로 설정합니다. 메인 루프의 조건 current !== null || stack.length > 0은 "아직 방문할 노드가 있거나 스택에 대기 중인 노드가 있으면 계속"을 의미합니다.
이 조건이 중요한데, current가 null이더라도 스택에 노드가 남아있으면 순회를 계속해야 하기 때문입니다. 두 번째로, 내부 while 루프에서 현재 노드에서 시작하여 가장 왼쪽 노드까지 경로의 모든 노드를 스택에 푸시합니다.
이는 중위 순회에서 "왼쪽 먼저" 규칙을 구현한 것입니다. 가장 왼쪽 노드(가장 작은 값)에 도달하면 내부 루프가 종료됩니다.
세 번째로, 스택에서 노드를 팝하여 처리합니다. 이 노드가 현재 순서상 방문해야 할 노드입니다.
값이 이전 값 이하라면 정렬이 깨진 것이므로 false를 반환합니다. 그렇지 않으면 prev를 업데이트하고, current를 오른쪽 자식으로 설정하여 오른쪽 서브트리를 탐색할 준비를 합니다.
오른쪽 자식이 있으면 메인 루프가 다시 그 노드의 왼쪽으로 내려갑니다. 여러분이 이 코드를 사용하면 재귀 제한 없이 어떤 크기의 트리도 안전하게 검증할 수 있습니다.
시간 복잡도는 O(n)으로 동일하지만, 공간 복잡도는 최악의 경우 O(n)입니다(편향 트리에서 모든 노드가 스택에 들어갈 수 있음). 하지만 평균적으로는 O(h)이며, 무엇보다 스택 오버플로우가 발생하지 않아 프로덕션 환경에 적합합니다.
실전 팁
💡 스택 크기를 모니터링하면 트리의 편향 정도를 파악할 수 있습니다. 최대 스택 크기가 트리 높이와 비슷하면 균형 잡힌 트리, 노드 수와 비슷하면 편향된 트리입니다.
💡 메모리 제약이 있는 환경에서는 스택 크기에 상한선을 두고, 초과 시 검증을 중단하거나 다른 방법으로 전환할 수 있습니다.
💡 디버깅 시 각 반복에서 스택 내용을 출력하면 순회 과정을 시각적으로 이해할 수 있습니다. 예: console.log('Stack:', stack.map(n => n.val))
💡 이 패턴은 모든 종류의 트리 순회(전위, 후위)를 반복적으로 구현할 때 사용할 수 있습니다. 노드를 스택에 넣고 꺼내는 순서만 조정하면 됩니다.
💡 성능 최적화를 위해 배열 대신 링크드 리스트 기반 스택을 사용하면 push/pop 연산이 더 효율적일 수 있습니다. 특히 매우 큰 트리에서 차이가 납니다.
4. Morris 순회 기반 검증 - O(1) 공간 복잡도
시작하며
여러분이 메모리가 극도로 제한된 임베디드 시스템이나 모바일 환경에서 대용량 트리를 처리해야 하는 상황을 만난 적 있나요? 스택이나 재귀는 O(h)의 공간이 필요한데, 메모리가 부족하면 사용할 수 없습니다.
이런 문제는 IoT 디바이스나 저사양 시스템에서 자주 발생합니다. 수백만 개의 노드를 가진 트리를 검증해야 하는데, 추가 메모리를 거의 사용할 수 없는 경우입니다.
일반적인 순회 방법은 메모리 부족으로 실패하거나 시스템을 다운시킬 수 있습니다. 바로 이럴 때 필요한 것이 Morris 순회입니다.
트리 자체의 구조를 임시로 변경하여 추가 공간 없이 순회하고, 완료 후 원상복구하는 혁신적인 방법입니다.
개요
간단히 말해서, 이 알고리즘은 트리의 빈 링크를 활용하여 스택이나 재귀 없이 중위 순회를 구현하는 고급 기법입니다. Morris 순회의 핵심 아이디어는 "threaded binary tree"를 임시로 만드는 것입니다.
각 노드의 중위 선행자(inorder predecessor)에서 현재 노드로 돌아오는 임시 링크를 만들어, 백트래킹 정보를 저장합니다. 예를 들어, 왼쪽 서브트리를 다 방문한 후 부모로 돌아와야 할 때, 이 임시 링크를 따라갑니다.
순회가 끝나면 모든 임시 링크를 제거하여 트리를 원상복구합니다. 기존 방법들이 스택에 부모 정보를 저장했다면, 이제는 트리 자체에 임시로 저장하여 O(1) 공간만 사용합니다.
이 알고리즘의 핵심 특징은 (1) 상수 공간만 사용하여 메모리 효율이 최고이고, (2) 트리 구조를 임시로 변경하지만 완료 후 복원하며, (3) 캐시 친화적이라 실제 성능이 좋다는 것입니다. 이러한 특징들이 메모리 제약이 심한 환경에서 유일한 해결책이 됩니다.
코드 예제
function isValidBST(root) {
let current = root;
let prev = -Infinity;
while (current !== null) {
if (current.left === null) {
// 왼쪽이 없으면 현재 노드 처리
if (current.val <= prev) return false;
prev = current.val;
current = current.right;
} else {
// 중위 선행자 찾기
let predecessor = current.left;
while (predecessor.right !== null && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
// 임시 링크 생성
predecessor.right = current;
current = current.left;
} else {
// 임시 링크 제거 및 노드 처리
predecessor.right = null;
if (current.val <= prev) return false;
prev = current.val;
current = current.right;
}
}
}
return true;
}
설명
이것이 하는 일: 이 함수는 스택이나 재귀 없이, 단지 몇 개의 포인터 변수만으로 트리를 중위 순회합니다. 핵심은 각 노드의 왼쪽 서브트리에서 가장 오른쪽 노드(중위 선행자)를 찾아, 그 노드의 오른쪽 링크를 현재 노드로 설정하는 것입니다.
첫 번째로, 메인 루프에서 current 노드에 왼쪽 자식이 없으면 그냥 처리합니다. 왼쪽 서브트리가 없다는 것은 현재 노드가 이 시점에서 가장 작은 값이라는 의미입니다.
값을 검증하고 prev를 업데이트한 후 오른쪽으로 이동합니다. 이는 Morris 순회의 가장 간단한 케이스입니다.
두 번째로, 왼쪽 자식이 있으면 중위 선행자를 찾습니다. 왼쪽 서브트리로 한 번 내려간 후, 오른쪽으로 계속 이동하여 가장 오른쪽 노드를 찾습니다.
단, predecessor.right가 이미 current를 가리키고 있으면 멈춥니다(이미 만든 임시 링크를 발견한 경우). 이 과정이 백트래킹 정보를 찾는 단계입니다.
세 번째로, 선행자의 오른쪽이 null이면 아직 이 서브트리를 방문하지 않은 것이므로 임시 링크를 만듭니다. predecessor.right = current로 설정하여 나중에 돌아올 길을 만들고, 왼쪽 서브트리로 내려갑니다.
반대로 선행자의 오른쪽이 이미 current를 가리키고 있으면, 왼쪽 서브트리를 모두 방문하고 돌아온 것입니다. 임시 링크를 제거(predecessor.right = null)하고, 현재 노드를 처리한 후 오른쪽으로 이동합니다.
여러분이 이 코드를 사용하면 어떤 크기의 트리도 상수 메모리만으로 검증할 수 있습니다. 시간 복잡도는 O(n)이지만 각 에지를 최대 3번 방문하므로 실제로는 약간 느릴 수 있습니다.
공간 복잡도는 O(1)로 다른 방법들보다 월등히 우수합니다. 단, 트리를 일시적으로 수정하므로 멀티스레드 환경에서는 주의가 필요합니다.
실전 팁
💡 Morris 순회는 read-only 상황이 아니므로, 동시성 제어가 필요한 환경에서는 락을 사용하거나 다른 방법을 선택하세요. 여러 스레드가 동시에 순회하면 임시 링크가 충돌합니다.
💡 디버깅이 어렵다면 각 단계에서 트리 상태를 시각화하세요. 임시 링크가 언제 생성되고 제거되는지 추적하면 알고리즘 이해에 큰 도움이 됩니다.
💡 predecessor를 찾는 루프에 무한 루프 방지 장치를 추가하면 안전합니다. 예: let steps = 0; while (...) { if (++steps > 10000) throw Error('Infinite loop detected'); }
💡 이 기법은 공간 복잡도가 정말 중요한 경우에만 사용하세요. 대부분의 실무 상황에서는 스택 기반 방법이 더 간단하고 안전합니다.
💡 트리 구조를 수정하므로, 예외가 발생하면 트리가 손상될 수 있습니다. try-finally 블록으로 감싸서 항상 원상복구되도록 보장하는 것이 좋습니다.
5. 재귀 + 서브트리 정보 반환 - 최적화된 검증
시작하며
여러분이 BST 검증을 하면서 "각 서브트리를 여러 번 검사하는 것 같은데, 더 효율적인 방법은 없을까?"라고 생각해본 적 있나요? 특히 대규모 트리에서 중복 연산을 줄이면 성능이 크게 향상될 수 있습니다.
이런 최적화는 실시간 시스템이나 고성능 애플리케이션에서 중요합니다. 예를 들어, 트리가 자주 수정되고 매번 검증해야 하는 상황에서는 불필요한 연산을 최소화해야 합니다.
단순히 각 노드를 검사하는 것보다, 서브트리의 정보를 재사용하면 더 효율적입니다. 바로 이럴 때 필요한 것이 서브트리 정보를 반환하는 최적화된 검증입니다.
각 서브트리의 최소/최대값을 함께 반환하여, 상위 레벨에서 불필요한 재탐색을 방지합니다.
개요
간단히 말해서, 이 알고리즘은 각 서브트리를 검증하면서 동시에 그 서브트리의 최소값과 최대값 정보를 반환하여, 부모 노드에서 추가 검증 없이 바로 사용할 수 있게 하는 방법입니다. 전통적인 재귀 방법은 각 노드에서 왼쪽/오른쪽 서브트리를 독립적으로 검증했습니다.
하지만 이 방법은 각 서브트리가 (1) 유효한 BST인지, (2) 최소값은 얼마인지, (3) 최대값은 얼마인지를 한 번에 계산하여 반환합니다. 예를 들어, 오른쪽 서브트리의 최소값이 현재 노드보다 크면 BST 속성을 만족하는 것을 즉시 알 수 있습니다.
기존 방법이 boolean만 반환했다면, 이제는 {isValid, min, max} 객체를 반환하여 더 많은 정보를 한 번의 재귀 호출로 얻습니다. 이 알고리즘의 핵심 특징은 (1) 서브트리 정보를 캐싱하여 중복 연산을 방지하고, (2) 한 번의 재귀로 여러 정보를 동시에 계산하며, (3) 상향식(bottom-up) 접근으로 효율성을 극대화한다는 것입니다.
이러한 특징들이 대규모 트리에서 성능 차이를 만듭니다.
코드 예제
function isValidBST(root) {
function validate(node) {
// 빈 노드는 유효, min/max는 null
if (node === null) {
return { isValid: true, min: null, max: null };
}
// 왼쪽과 오른쪽 서브트리 검증
const left = validate(node.left);
const right = validate(node.right);
// 서브트리가 무효하면 즉시 반환
if (!left.isValid || !right.isValid) {
return { isValid: false, min: null, max: null };
}
// BST 속성 체크: 왼쪽 최대 < 현재 < 오른쪽 최소
if ((left.max !== null && left.max >= node.val) ||
(right.min !== null && right.min <= node.val)) {
return { isValid: false, min: null, max: null };
}
// 현재 서브트리의 min/max 계산
const min = left.min !== null ? left.min : node.val;
const max = right.max !== null ? right.max : node.val;
return { isValid: true, min, max };
}
return validate(root).isValid;
}
설명
이것이 하는 일: 이 함수는 후위 순회(post-order) 방식으로 트리를 탐색하며, 각 노드에서 서브트리의 정보를 수집하고 검증합니다. 리프에서 시작하여 루트로 올라가면서 정보를 누적합니다.
첫 번째로, 베이스 케이스에서 null 노드는 유효한 빈 트리로 처리합니다. min과 max를 null로 설정하는 것이 중요한데, 이는 "값이 없음"을 명시적으로 표현하여 부모 노드에서 올바르게 처리할 수 있게 합니다.
빈 서브트리는 어떤 조건도 위반하지 않습니다. 두 번째로, 양쪽 서브트리를 재귀적으로 검증하고 결과를 받습니다.
각 결과 객체에는 isValid, min, max가 포함됩니다. 둘 중 하나라도 유효하지 않으면 현재 서브트리도 유효하지 않으므로 즉시 false를 반환합니다.
이는 조기 종료 최적화로, 무효한 서브트리를 발견하면 더 이상 계산하지 않습니다. 세 번째로, 양쪽 서브트리가 모두 유효하면 BST 속성을 체크합니다.
왼쪽 서브트리의 최대값이 현재 노드 값 이상이거나, 오른쪽 서브트리의 최소값이 현재 노드 값 이하면 속성 위반입니다. null 체크를 먼저 하여 빈 서브트리를 안전하게 처리합니다.
마지막으로 현재 서브트리의 최소값(왼쪽 서브트리의 최소값 또는 현재 노드 값)과 최대값(오른쪽 서브트리의 최대값 또는 현재 노드 값)을 계산하여 반환합니다. 여러분이 이 코드를 사용하면 각 노드를 정확히 한 번씩만 방문하면서도 필요한 모든 정보를 수집할 수 있습니다.
시간 복잡도는 O(n)이지만 실제로는 다른 방법보다 빠를 수 있습니다. 공간 복잡도는 O(h)로 재귀 스택만 사용하며, 추가적인 정보 저장으로 인한 오버헤드가 거의 없습니다.
특히 트리가 크고 균형 잡혀 있을수록 효율성이 두드러집니다.
실전 팁
💡 min/max를 null이 아닌 -Infinity/Infinity로 초기화하면 null 체크를 생략할 수 있지만, 실제 노드 값이 Infinity일 수 있으므로 주의하세요.
💡 이 패턴은 메모이제이션과 결합하여 동적 계획법 문제에 응용할 수 있습니다. 예를 들어, 각 서브트리의 결과를 캐시에 저장하여 반복 쿼리를 최적화할 수 있습니다.
💡 디버깅 시 각 노드에서 반환하는 객체를 로깅하면 정보가 어떻게 전파되는지 추적할 수 있습니다. 예: console.log(Node ${node.val}: min=${min}, max=${max})
💡 이 방법은 다른 트리 문제에도 유용합니다. 예를 들어, 서브트리의 크기, 높이, 합계 등을 함께 반환하는 패턴으로 확장할 수 있습니다.
💡 객체 생성 오버헤드가 걱정된다면, 배열 [isValid, min, max]를 사용하거나, 클래스 인스턴스 풀링을 고려하세요. 하지만 대부분의 경우 객체 생성 비용은 무시할 만합니다.
6. 범위 체크 최적화 - 정수 오버플로우 처리
시작하며
여러분이 BST 검증 코드를 작성하면서 노드 값이 정수 범위의 최소값이나 최대값일 때 예상치 못한 버그를 만난 적 있나요? 예를 들어, 노드 값이 -2147483648(INT_MIN)인데 초기 min이 -Infinity라면 문제없지만, 실제 정수 비교에서는 예외가 발생할 수 있습니다.
이런 문제는 코딩 인터뷰나 실무에서 자주 간과되는 엣지 케이스입니다. 특히 C++, Java처럼 정수 타입이 명확한 언어로 포팅할 때 문제가 됩니다.
JavaScript는 Number 타입이 유연하지만, 다른 언어에서는 오버플로우나 타입 에러가 발생할 수 있습니다. 바로 이럴 때 필요한 것이 null을 활용한 범위 체크 최적화입니다.
Infinity 대신 null을 사용하여 "제약 없음"을 명시적으로 표현하고, 정수 범위 문제를 원천적으로 방지합니다.
개요
간단히 말해서, 이 알고리즘은 min/max 범위를 Infinity 대신 null로 표현하여, 정수 오버플로우와 타입 불일치 문제를 방지하는 안전한 구현 방법입니다. null을 사용하면 "범위 제약이 없음"을 명확히 나타낼 수 있습니다.
초기 호출 시 min과 max를 null로 전달하면, 루트 노드는 어떤 값이든 가질 수 있습니다. 예를 들어, 노드 값이 Number.MAX_SAFE_INTEGER더라도 max가 null이므로 체크를 건너뜁니다.
이는 언어 간 이식성도 높입니다. 기존 방법이 Infinity를 사용하여 암묵적으로 "제약 없음"을 표현했다면, 이제는 null을 사용하여 명시적으로 표현합니다.
이 알고리즘의 핵심 특징은 (1) 모든 정수 값을 안전하게 처리하고, (2) 코드의 의도가 명확하여 가독성이 높으며, (3) 다른 프로그래밍 언어로 쉽게 포팅할 수 있다는 것입니다. 이러한 특징들이 프로덕션 코드의 안정성과 유지보수성을 향상시킵니다.
코드 예제
function isValidBST(root, min = null, max = null) {
// 빈 노드는 유효한 BST
if (root === null) return true;
// min이 null이 아니면 현재 값이 min보다 커야 함
if (min !== null && root.val <= min) return false;
// max가 null이 아니면 현재 값이 max보다 작아야 함
if (max !== null && root.val >= max) return false;
// 왼쪽: max를 현재 값으로, 오른쪽: min을 현재 값으로
return isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max);
}
설명
이것이 하는 일: 이 함수는 첫 번째 섹션의 범위 기반 검증과 동일한 로직을 사용하지만, Infinity 대신 null을 사용하여 더 안전하고 명시적으로 구현합니다. 각 단계에서 null 체크를 명확히 수행합니다.
첫 번째로, 초기 호출 시 min과 max를 명시적으로 null로 설정합니다. 이는 "루트 노드에 대한 제약이 없음"을 의미합니다.
베이스 케이스에서 null 노드를 만나면 true를 반환하는 것은 동일합니다. 두 번째로, 범위 체크에서 min이 null이 아닐 때만 비교를 수행합니다.
min이 null이면 하한선이 없다는 의미이므로 체크를 건너뜁니다. 마찬가지로 max가 null이 아닐 때만 상한선 체크를 수행합니다.
이렇게 하면 root.val이 어떤 극단적인 값이어도 안전하게 처리됩니다. 세 번째로, 재귀 호출에서 범위를 업데이트합니다.
왼쪽으로 갈 때는 max를 현재 값으로 설정하고 min은 그대로 전달합니다. 오른쪽으로 갈 때는 min을 현재 값으로 설정하고 max는 그대로 전달합니다.
null이 계속 전파되어 해당 방향의 제약이 없음을 유지합니다. 여러분이 이 코드를 사용하면 INT_MIN, INT_MAX, Number.MAX_SAFE_INTEGER 같은 극단적인 값도 올바르게 처리할 수 있습니다.
코드의 의도가 명확하여 다른 개발자가 읽기 쉽고, 코드 리뷰나 인터뷰에서 좋은 인상을 줄 수 있습니다. 시간 및 공간 복잡도는 Infinity 버전과 동일하지만, null 체크로 인한 약간의 오버헤드가 있습니다(무시할 수준).
실전 팁
💡 TypeScript를 사용한다면 타입을 명시하세요. isValidBST(root: TreeNode | null, min: number | null = null, max: number | null = null): boolean
💡 null 체크 순서를 바꾸면 성능이 약간 향상될 수 있습니다. 무효한 케이스를 먼저 체크하여 조기 종료하세요.
💡 이 패턴은 범위 쿼리, 구간 트리, 세그먼트 트리 등 다양한 자료구조에서 범위를 다룰 때 유용합니다.
💡 Java나 C++ 같은 언어로 포팅할 때는 Integer 객체나 Optional을 사용하여 null을 표현하세요. 프리미티브 타입으로는 null을 나타낼 수 없습니다.
💡 단위 테스트를 작성할 때 [INT_MIN], [INT_MAX], [INT_MIN, null, INT_MAX] 같은 극단적인 케이스를 반드시 포함하세요. 이들이 가장 흔한 버그 원인입니다.
7. 배열 기반 빠른 검증 - 중위 순회 결과 비교
시작하며
여러분이 BST 검증을 여러 번 수행하거나, 검증 결과를 다른 용도로 재사용하고 싶은 상황을 만난 적 있나요? 예를 들어, 트리가 유효한지 확인한 후 정렬된 값들의 리스트도 필요한 경우가 있습니다.
이런 상황은 실무에서 자주 발생합니다. BST를 검증하면서 동시에 정렬된 데이터를 추출하거나, 검증 과정을 로깅하거나, 시각화를 위해 순회 결과를 저장해야 하는 경우입니다.
기존 방법들은 boolean만 반환하여 추가 작업이 필요했습니다. 바로 이럴 때 필요한 것이 배열 기반 검증입니다.
중위 순회로 배열을 생성하고, 그 배열이 정렬되어 있는지 확인하는 방식으로 검증과 데이터 추출을 동시에 수행합니다.
개요
간단히 말해서, 이 알고리즘은 트리를 중위 순회하여 모든 값을 배열에 담고, 그 배열이 오름차순인지 확인하는 두 단계 접근법입니다. 첫 번째 단계에서 중위 순회로 모든 노드 값을 배열에 수집합니다.
두 번째 단계에서 배열을 순회하며 각 요소가 이전 요소보다 큰지 확인합니다. 예를 들어, 배열이 [1, 3, 5, 7]이면 유효한 BST이고, [1, 5, 3, 7]이면 무효합니다.
이 방법의 장점은 순회 결과를 재사용할 수 있다는 것입니다. 기존 방법들이 순회와 검증을 동시에 수행했다면, 이제는 명확히 분리하여 각 단계를 독립적으로 테스트하고 디버깅할 수 있습니다.
이 알고리즘의 핵심 특징은 (1) 순회 결과를 배열로 저장하여 재사용 가능하고, (2) 로직이 두 단계로 분리되어 이해하기 쉬우며, (3) 디버깅과 시각화가 용이하다는 것입니다. 이러한 특징들이 개발 과정에서 유용하지만, 메모리 사용량이 O(n)으로 증가하는 트레이드오프가 있습니다.
코드 예제
function isValidBST(root) {
const values = [];
// 중위 순회로 값 수집
function inorder(node) {
if (node === null) return;
inorder(node.left);
values.push(node.val);
inorder(node.right);
}
inorder(root);
// 배열이 정렬되어 있는지 확인
for (let i = 1; i < values.length; i++) {
if (values[i] <= values[i - 1]) {
return false;
}
}
return true;
}
설명
이것이 하는 일: 이 함수는 트리 검증을 두 개의 명확한 단계로 분리합니다. 첫 번째 단계는 데이터 수집, 두 번째 단계는 검증입니다.
각 단계가 독립적으로 작동하여 테스트와 유지보수가 쉽습니다. 첫 번째로, 빈 배열 values를 생성하고 중위 순회 함수를 정의합니다.
inorder 함수는 재귀적으로 왼쪽 → 현재 → 오른쪽 순서로 노드를 방문하며, 각 노드의 값을 배열에 추가합니다. 이는 표준적인 중위 순회 패턴으로, BST에서 값들을 정렬된 순서로 수집하는 가장 직관적인 방법입니다.
두 번째로, 순회가 완료되면 values 배열에 트리의 모든 값이 중위 순회 순서로 저장됩니다. 이 시점에서 배열을 다른 용도로 사용할 수 있습니다(로깅, 반환, 시각화 등).
배열이 비어있으면(빈 트리) for 루프를 실행하지 않고 true를 반환합니다. 세 번째로, for 루프에서 배열을 순회하며 정렬 상태를 확인합니다.
i번째 요소가 i-1번째 요소 이하라면 정렬이 깨진 것이므로 즉시 false를 반환합니다. 모든 요소가 정렬되어 있으면 루프가 끝나고 true를 반환합니다.
이 단계는 O(n) 시간이 걸리지만 매우 간단하고 명확합니다. 여러분이 이 코드를 사용하면 검증 결과뿐만 아니라 정렬된 값의 배열도 얻을 수 있습니다.
시간 복잡도는 O(n) + O(n) = O(n)으로 동일하지만, 공간 복잡도는 O(n)으로 배열 저장 비용이 추가됩니다. 노드 수가 많은 대규모 트리에서는 메모리 부담이 있지만, 중소규모 트리나 디버깅 용도로는 매우 유용합니다.
실전 팁
💡 순회 결과를 반환하려면 함수를 수정하세요. return { isValid: true, values } 형태로 반환하면 검증과 데이터를 동시에 얻을 수 있습니다.
💡 큰 트리에서는 제너레이터를 사용하여 메모리를 절약할 수 있습니다. function* inorder(node)로 정의하고 yield로 값을 하나씩 생성하면서 검증하세요.
💡 이 방법은 테스트 작성에 매우 유용합니다. 예상되는 배열과 실제 배열을 비교하면 어느 노드에서 문제가 발생했는지 정확히 파악할 수 있습니다.
💡 디버깅 시 values 배열을 출력하면 트리 구조를 빠르게 이해할 수 있습니다. console.log('Inorder:', values)
💡 이 패턴을 다른 검증과 결합할 수 있습니다. 예를 들어, 중복 값 체크, 특정 값 존재 여부 확인 등을 배열 메서드(Set, includes 등)를 활용하여 쉽게 구현할 수 있습니다.
8. 경계 조건 강화 - 중복 값 허용 BST
시작하며
여러분이 실무에서 BST를 구현하다가 "중복 값을 어떻게 처리해야 하지?"라는 고민을 해본 적 있나요? 표준 BST는 중복을 허용하지 않지만, 실제 애플리케이션에서는 중복 값을 허용해야 하는 경우가 많습니다.
이런 상황은 실제로 자주 발생합니다. 예를 들어, 타임스탬프가 같은 이벤트들을 저장하거나, 동일한 우선순위를 가진 작업들을 관리할 때 중복 값이 필요합니다.
전통적인 BST 정의를 약간 수정하여 "왼쪽 ≤ 현재 < 오른쪽" 또는 "왼쪽 < 현재 ≤ 오른쪽" 규칙을 적용할 수 있습니다. 바로 이럴 때 필요한 것이 중복 값 허용 BST 검증입니다.
등호 조건을 조정하여 한쪽 서브트리에 같은 값을 허용하는 변형 BST를 검증합니다.
개요
간단히 말해서, 이 알고리즘은 전통적인 BST 규칙을 수정하여 중복 값을 허용하되, 여전히 검색 효율성을 유지하는 변형 BST를 검증하는 방법입니다. 중복 값을 허용하는 BST의 일반적인 규칙은 "왼쪽 서브트리 ≤ 현재 노드 < 오른쪽 서브트리"입니다.
이는 같은 값들이 모두 왼쪽에 모이도록 하여 일관성을 유지합니다. 예를 들어, [5, 5, 5, 7] 같은 순서가 유효합니다.
반대로 "왼쪽 < 현재 ≤ 오른쪽" 규칙을 사용할 수도 있지만, 한 가지 규칙을 일관되게 적용해야 합니다. 기존 BST 검증이 모든 등호를 거부했다면, 이제는 한쪽 방향에서 등호를 허용하여 중복을 수용합니다.
이 알고리즘의 핵심 특징은 (1) 실무에서 자주 필요한 중복 값 처리를 지원하고, (2) 검색 효율성을 유지하며, (3) 규칙을 명확히 정의하여 일관성을 보장한다는 것입니다. 이러한 특징들이 실제 애플리케이션에서 BST를 더 유연하게 활용할 수 있게 합니다.
코드 예제
function isValidBSTWithDuplicates(root, min = null, max = null) {
if (root === null) return true;
// 왼쪽: 현재 값 이하 허용 (등호 포함)
if (min !== null && root.val < min) return false;
// 오른쪽: 현재 값보다 커야 함 (등호 제외)
if (max !== null && root.val >= max) return false;
// 왼쪽으로 갈 때는 max를 포함하여 같은 값 허용
// 오른쪽으로 갈 때는 min을 제외하여 큰 값만 허용
return isValidBSTWithDuplicates(root.left, min, root.val) &&
isValidBSTWithDuplicates(root.right, root.val, max);
}
설명
이것이 하는 일: 이 함수는 범위 기반 검증의 변형으로, 등호 조건을 조정하여 중복 값을 한쪽 서브트리에 허용합니다. 규칙을 일관되게 적용하여 트리의 검색 효율성을 유지합니다.
첫 번째로, 베이스 케이스와 초기 설정은 표준 BST 검증과 동일합니다. null 노드는 유효하고, min과 max는 null로 초기화됩니다.
차이점은 범위 체크에서 등호 처리입니다. 두 번째로, 하한선 체크에서 root.val < min을 사용합니다(이전에는 <=).
이는 현재 노드 값이 min과 같아도 괜찮다는 의미입니다. 즉, 왼쪽 서브트리에서 올라온 값과 같은 값을 허용합니다.
상한선 체크는 여전히 root.val >= max를 사용하여 오른쪽에는 반드시 큰 값만 허용합니다. 세 번째로, 재귀 호출에서 범위 업데이트는 동일합니다.
왼쪽으로 갈 때 max를 현재 값으로 설정하는데, 위에서 등호를 허용하므로 왼쪽 서브트리에 같은 값이 있을 수 있습니다. 오른쪽으로 갈 때 min을 현재 값으로 설정하는데, 등호를 제외하므로 오른쪽 서브트리는 반드시 현재 값보다 커야 합니다.
이 규칙이 트리 전체에 일관되게 적용됩니다. 여러분이 이 코드를 사용하면 타임스탬프, 우선순위, 점수 같은 중복 가능한 데이터를 BST로 관리할 수 있습니다.
시간 및 공간 복잡도는 표준 BST 검증과 동일하지만, 더 넓은 범위의 트리를 유효한 것으로 인정합니다. 주의할 점은 중복 값이 많으면 트리가 불균형해질 수 있어 재조정 로직(AVL, Red-Black 등)이 필요할 수 있습니다.
실전 팁
💡 중복 값을 오른쪽에 허용하려면 조건을 반대로 바꾸세요. root.val <= min과 root.val > max로 변경하면 됩니다. 하지만 한 번 정한 규칙은 일관되게 유지해야 합니다.
💡 중위 순회 기반 검증에서 중복을 허용하려면 node.val < prev로 변경하세요. 등호를 제거하여 같은 값을 허용합니다.
💡 실무에서는 중복 값 처리 정책을 문서화하세요. "같은 값은 왼쪽 서브트리에 저장"같은 규칙을 명시하여 팀원들이 이해할 수 있게 합니다.
💡 삽입/삭제 로직도 같은 규칙을 따라야 합니다. 검증만 중복을 허용하고 삽입은 거부하면 일관성이 깨집니다.
💡 중복 값이 매우 많다면 각 노드에 카운터를 추가하는 방법을 고려하세요. 같은 값을 여러 노드로 저장하는 대신, 한 노드에 count 필드를 두어 메모리를 절약할 수 있습니다.