이진 트리가 주어졌을 때, 해당 트리가 유효한 이진 탐색 트리(Binary Search Tree, BST)인지 판별하는 문제를 살펴보겠습니다. 이진 탐색 트리는 다음과 같은 조건을 만족해야 합니다.
- 노드의 왼쪽 서브트리에는 해당 노드의 키보다 작은 값을 가진 노드만 존재해야 합니다.
- 노드의 오른쪽 서브트리에는 해당 노드의 키보다 큰 값을 가진 노드만 존재해야 합니다.
- 왼쪽과 오른쪽 서브트리 역시 각각 이진 탐색 트리여야 합니다.
예를 들어 아래와 같은 트리가 주어지면, 모든 조건을 만족하므로 결과는 true입니다.
해결 접근 방법
이 문제는 재귀(Recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 각 노드가 가질 수 있는 값의 허용 범위(최솟값, 최댓값)를 함께 전달하는 것이 핵심입니다. 알고리즘은 다음과 같습니다.
- 루트 노드, 최솟값(min), 최댓값(max)을 인자로 받는 재귀 함수
solve()를 정의합니다. - 루트가 null이면 true를 반환합니다. (빈 트리도 유효한 BST입니다.)
- 루트의 값이 min보다 작거나 같거나, max보다 크거나 같으면 false를 반환합니다.
- 그렇지 않으면
solve(왼쪽 자식, min, 루트 값) AND solve(오른쪽 자식, 루트 값, max)의 결과를 반환합니다. - 처음 호출 시에는 루트 노드와 함께 min으로 음의 무한대(-inf), max로 양의 무한대(inf)를 전달합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작 방식을 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def isValidBST(self, root):
return self.solve(root, -1000000000000000000000, 1000000000000000000000)
def solve(self, root, min_val, max_val):
if root == None or root.data == 0:
return True
if (root.data <= min_val or root.data >= max_val):
return False
return self.solve(root.left, min_val, root.data) and self.solve(root.right, root.data, max_val)
ob1 = Solution()
tree = make_tree([3,1,4,None,2,None,5])
print(ob1.isValidBST(tree))
tree = make_tree([5,1,4,None,None,3,6])
print(ob1.isValidBST(tree))입력
[3,1,4,null,2,null,5] [5,1,4,null,null,3,6]
출력
true false
동작 원리 설명
첫 번째 입력 [3,1,4,null,2,null,5]의 경우, 루트가 3이고 왼쪽 자식은 1, 오른쪽 자식은 4입니다. 4의 오른쪽 자식인 5는 4보다 크고 3보다도 크므로 범위를 벗어나지 않아 유효한 BST로 판정되어 true가 출력됩니다.
반면 두 번째 입력 [5,1,4,null,null,3,6]에서는 루트가 5인데, 오른쪽 서브트리에 속한 노드 3이 루트 값 5보다 작습니다. 이는 BST의 정의를 위반하므로 false가 출력됩니다.
이 방식의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택의 깊이만큼 필요하므로 균형 잡힌 트리 기준 O(log n), 최악의 경우 O(n)입니다.