[BST] Is Binary Search Tree?
난이도: ★★☆☆☆ • solved on: 2025-12-07
WARNING!
이 문제의 경우, Hackerrank의 테스트 구조에 문제가 생겨 직접 submission을 하지는 못했습니다.
Hackerrank는 기본적으로 Solution Class를 통해 우리의 코드를 점검함
그런데 이 문제는 Solution Class가 없고 대신 Tree Class가 있음
그러면 정상적인 흐름은 테스트 코드는 Tree로 인식을 하고 해야함. 하지만 이 문제에서는 여전히 Solution Class를 찾고 있음 (???)
그래서 결론적으로 아래와 같은 오류가 발생함 (하지만 이건 boilertemplate 설정의 영향이 커 다른 언어를 안다면 그것으로 진행하면 된다.)
문제 요약
- 문제 유형: 트리(Tree), BST 검증, 재귀(DFS)
- 요구사항: 주어진 이진 트리가 BST(Binary Search Tree)의 조건을 만족하는지 판별해야 한다.
사용 개념
-
자료구조
- Binary Tree
- Node(left, right, data)
-
알고리즘/기법
- DFS 재귀 탐색
- min-max 범위 제한 기법(BST 검증 정석 방식)
-
핵심 키워드
- BST property
- global constraint (min, max)
- subtree validation
풀이 아이디어 및 코드
방법 1 : 처음 시도한 내 풀이 (실패 원인 분석을 위해 남김)
1. 문제 분해
- 왼쪽 자식의 값이 root보다 크면 BST 위반
- 오른쪽 자식의 값이 root보다 작으면 BST 위반
- 그렇지 않으면 각각 subtree로 재귀 이동
2. 작성 코드
boolean checkBST(Node root) {
if(root == null){
return false;
}
if(root.left != null){
if(root.data < root.left.data){
return false;
} else {
return checkBST(root.left);
}
}
if(root.right != null){
if(root.right.data < root.data){
return false;
} else {
return checkBST(root.right);
}
}
return true;
}3. 실패 원인 분석
① 자식 노드와의 비교만 수행함 (즉 바로 위의 부모 노드에 대한 검증만 한다)
BST는 “왼쪽 subtree 전체 < root, 오른쪽 subtree 전체 > root”가 기준이다.
위 코드는 직접 자식만 비교하기 때문에 subtree 깊은 곳의 위반을 검출할 수 없다.
예:
10
/
5
\
20 ← BST 위반20은 10보다 크므로 BST 위반이지만 내 코드는 통과시킨다.
② null을 false로 처리하여 leaf 자식에서 잘못된 결과 발생
BST 여부 판정에서 null은 정상 종료 지점이다.
따라서 true여야 하지만 내 코드는 false를 반환한다.
방법 2 : 개선된 BST 풀이
1. 문제 분해
- 각 노드는 (
min < node.data < max)의 범위 내에 있어야 한다. - 왼쪽 subtree는 (
min,root.data) - 오른쪽 subtree는 (
root.data,max) - 이 범위를 재귀적으로 전달하면서 전체 트리를 검사한다.
2. 코드
boolean checkBST(Node root) {
return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
boolean validate(Node node, int min, int max) {
if (node == null) {
return true;
}
if (node.data <= min || node.data >= max) {
return false;
}
return validate(node.left, min, node.data)
&& validate(node.right, node.data, max);
}3. 핵심 로직 흐름
문제에서 애초에 추가적인 helper function이 필요할거라고 넌지시 힌트를 준다.
Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.
validate(node, min, max):
1. node가 null이면 true
2. node.data가 (min, max) 범위를 벗어나면 false
3. 왼쪽 subtree → (min, node.data)
4. 오른쪽 subtree → (node.data, max)
5. 두 subtree 모두 true면 BST4. 예외 처리
- null 입력은 BST로 간주 → true
- 중복 값이 존재하면 BST 아님
시간·공간 복잡도
방법 2 (정답 풀이)
- 시간 복잡도: O(N)
- 공간 복잡도: O(H) — 트리 높이만큼 재귀 stack 사용
어려웠던 점
- 처음에는 "직접 자식 비교만 하면 충분하다"라고 생각했지만, subtree 전체의 BST 조건을 놓친다는 근본적 오류를 나중에야 파악했다.
- left/right 각각을 검사하면서도 “전체 트리 관점의 범위 조건”을 전달해야 한다는 개념이 처음에는 이해되지 않았다.
- null을 BST의 정상 종료 지점(true)로 취급해야 한다는 점을 놓쳐서 false가 연쇄적으로 타고 올라가 전체 결과를 실패로 만들었다.
배운 점 및 팁
- BST 검증은 min-max 범위 검사 방식이 정석이며 실제 면접에서도 자주 묻는 방식이다.
- 단순히 “자식만 비교하는 방식”은 BST 검증을 절대 정확히 수행할 수 없다.
- 왼쪽과 오른쪽 자식 모두 검사해야 하며, return 시점에 유의해야 한다.
- null은 BST에서 정상 종료를 의미하므로 true 처리한다.
참고 및 링크
-
참고 블로그/깃허브: 없음
추가 연습 문제
-
비슷한 유형 (GPT 추천) :
-
확장 문제 (GPT 추천) :
