이진 트리가 주어졌을 때, 해당 트리가 이진 탐색 트리(Binary Search Tree, BST)인지 판별하는 문제입니다. BST는 다음과 같은 성질을 만족해야 합니다.
- 현재 노드보다 작은 값은 모두 왼쪽 서브트리에 위치합니다.
- 현재 노드보다 큰 값은 모두 오른쪽 서브트리에 위치합니다.
- 이 성질은 모든 노드에 대해 재귀적으로 유지되어야 합니다.
예를 들어 아래와 같은 트리가 입력으로 주어지면,
출력 결과는 True가 됩니다.
풀이 접근 방법
BST의 핵심 특징은 중위 순회(Inorder Traversal)를 수행하면 항상 오름차순으로 정렬된 결과가 나온다는 점입니다. 이를 활용하면 다음과 같이 문제를 해결할 수 있습니다.
- 트리의 요소들을 중위 순회하여 리스트 x에 저장합니다.
- x가 정렬되어 있다면 true를 반환합니다.
- 그렇지 않다면 false를 반환합니다.
구현 예제
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): def inorder(root, l): if root is None: return inorder(root.left, l) l.append(root.data) inorder(root.right, l) l = [] inorder(root, l) return l == sorted(l) 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))
입력
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)
출력
True
복잡도 분석 및 참고 사항
중위 순회에는 O(n)의 시간이 걸리고, 정렬 여부를 비교하는 데 추가로 O(n) 또는 정렬 기준에 따라 O(n log n)의 시간이 소요됩니다. 공간 복잡도는 순회 결과를 저장하는 리스트 때문에 O(n)입니다.
더 최적화하고 싶다면 리스트를 만들지 않고, 각 노드에 허용되는 값의 범위(min, max)를 재귀적으로 전달하며 검사하는 방법도 있습니다. 이 경우 O(n) 시간과 트리 높이만큼의 재귀 스택 공간만으로 BST 여부를 판별할 수 있습니다.