이진 탐색 트리(BST)가 주어지고, 왼쪽 경계 l과 오른쪽 경계 r이 함께 제공된다고 가정해 봅시다. 이때 루트 노드를 기준으로 값이 l 이상 r 이하(경계값 포함)인 모든 노드의 개수를 구하는 것이 목표입니다.
예를 들어 다음과 같은 BST가 있다고 가정해 보겠습니다.
여기서 l = 7, r = 13이라면, 값이 7 이상 13 이하인 노드는 8, 10, 12로 총 3개이므로 출력 결과는 3이 됩니다.
문제 해결 접근 방법
이 문제는 스택을 활용한 반복적 순회(iterative traversal) 방식으로 효율적으로 해결할 수 있습니다. BST의 핵심 성질, 즉 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다는 특성을 활용하면 불필요한 탐색을 줄일 수 있습니다.
알고리즘 단계
스택을 생성하고 루트 노드를 삽입한 뒤, 카운트 변수 count를 0으로 초기화합니다.
스택이 빌 때까지 다음 과정을 반복합니다.
스택의 최상단 요소를 꺼내 node에 저장합니다.
node가 null이 아닌 경우 다음을 수행합니다.
만약 l ≤ node.data ≤ r 이라면:
count를 1 증가시킵니다.
node의 오른쪽 자식과 왼쪽 자식을 모두 스택에 push합니다. (현재 노드가 범위 안에 있으므로 양쪽 자식 모두 확인 필요)
그렇지 않고 node.data < l 이라면:
오른쪽 자식만 스택에 push합니다. (현재 노드와 왼쪽 서브트리는 모두 l보다 작으므로 확인할 필요 없음)
그 외의 경우(node.data > r):
왼쪽 자식만 스택에 push합니다. (현재 노드와 오른쪽 서브트리는 모두 r보다 크므로 확인할 필요 없음)
반복이 끝나면 count를 반환합니다.
이처럼 각 단계에서 조건에 맞지 않는 서브트리 전체를 가지치기(pruning)하기 때문에, 일반적인 전체 순회보다 더 적은 노드만 방문하게 되어 시간 복잡도 측면에서 유리합니다.
예제 코드
from collections import deque
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, l, r):
stack, count = [root], 0
while stack:
node = stack.pop()
if node:
if l <= node.data <= r:
count += 1
stack += [node.right, node.left]
elif node.data < l:
stack += [node.right]
else:
stack += [node.left]
return count
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 7, 13))입력
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) l = 7, r = 13
출력
3
복잡도 분석
시간 복잡도: 최악의 경우 O(n)입니다. 모든 노드가 범위 내에 있으면 트리의 모든 노드를 방문해야 하기 때문입니다. 하지만 범위가 좁을수록 가지치기 효과로 실제 방문 노드 수는 크게 줄어듭니다.
공간 복잡도: O(h)입니다. 여기서 h는 트리의 높이로, 스택에는 한 번에 최대 트리 높이만큼의 노드만 저장되기 때문입니다.