Python으로 이진 탐색 트리(BST)에서 특정 값이 존재하는지 확인하는 방법

이진 탐색 트리(Binary Search Tree, BST)와 하나의 값 val이 주어졌을 때, 이 값이 트리 안에 존재하는지 확인하는 프로그램을 만들어 보겠습니다.

예를 들어 아래와 같은 트리가 있다고 가정해 봅시다.

만약 val = 7이라면, 7은 트리에 존재하므로 결과는 True가 됩니다.

풀이 접근 방법

BST의 핵심 성질을 활용하면 매 단계마다 탐색 범위를 절반으로 줄일 수 있습니다. 알고리즘은 다음과 같습니다.

• 루트 노드(root)와 값(val)을 인자로 받는 solve() 함수를 정의합니다.
• 현재 노드가 null이면 해당 값이 트리에 없다는 뜻이므로 False를 반환합니다.
• 현재 노드의 데이터가 val과 같으면 값을 찾은 것이므로 True를 반환합니다.
• 현재 노드의 데이터가 val보다 크면, BST 성질상 더 작은 값은 왼쪽 서브트리에 있으므로 왼쪽 자식으로 재귀 호출합니다.
• 그 외의 경우(현재 노드의 데이터가 val보다 작은 경우)에는 오른쪽 자식으로 재귀 호출합니다.

구현 예제

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, val):
        if not root:
            return False
        if root.data == val:
            return True
        if root.data > val:
            return self.solve(root.left, val)
        return self.solve(root.right, val)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root, 7))

입력

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
val = 7

출력

True

복잡도 분석

균형 잡힌 BST에서는 매번 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)입니다. 반면 트리가 한쪽으로 치우친 편향된 형태라면 최악의 경우 O(n)까지 증가할 수 있습니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 O(log n) ~ O(n)입니다.