Python으로 BST의 모든 내부 노드가 자식을 하나만 가지는지 확인하는 방법

문제 개요

이진 탐색 트리(BST)의 전위 순회(preorder traversal) 결과가 주어졌을 때, 트리의 모든 내부 노드가 자식을 정확히 하나만 가지고 있는지 확인하는 문제입니다.

예를 들어, 입력이 preorder = [22, 12, 13, 15, 14]라면 출력은 True가 됩니다. 이 전위 순회에 해당하는 BST는 다음과 같습니다.

접근 방법

이 문제를 효율적으로 해결하려면 BST의 핵심 성질을 활용할 수 있습니다. 즉, 어떤 노드의 모든 자손(descendant)은 그 노드보다 작거나 큰 값이어야 한다는 점입니다. 이를 바탕으로 다음과 같은 절차를 따릅니다.

• 현재 노드의 바로 다음 전위 순회 값(다음 후속 노드)을 확인합니다.
• 전위 순회의 마지막 값(마지막 후속 노드)을 확인합니다.
• 두 값이 현재 노드보다 모두 작거나 모두 크다면 계속 진행하고, 하나는 작고 하나는 크다면 False를 반환합니다.

직관적으로 설명하면, 어떤 노드가 두 개의 자식을 가지고 있다면 왼쪽 서브트리에는 더 작은 값들이, 오른쪽 서브트리에는 더 큰 값들이 존재하게 됩니다. 전위 순회는 루트를 먼저 방문한 뒤 왼쪽 서브트리, 오른쪽 서브트리 순으로 진행되므로, 바로 다음 값과 마지막 값이 현재 노드를 기준으로 부호가 반대라면 해당 노드가 두 자식을 가진다는 의미입니다.

알고리즘 단계

1. next와 last를 0으로 초기화합니다.
2. i를 0부터 preorder 길이 - 2까지 반복하며 다음을 수행합니다.
   • next = preorder[i] - preorder[i+1]
   • last = preorder[i] - preorder[-1]
   • next * last < 0이면 False를 반환합니다.
3. 반복이 정상적으로 끝나면 True를 반환합니다.

예제 코드

def solve(preorder):
    next = 0
    last = 0
    for i in range(len(preorder)-1):
        next = preorder[i] - preorder[i+1]
        last = preorder[i] - preorder[-1]
        if next * last < 0:
            return False
    return True

preorder = [22, 12, 13, 15, 14]
print(solve(preorder))

입력

[22, 12, 13, 15, 14]

출력

True

복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간 없이 상수 공간 O(1)만 사용하기 때문에 매우 효율적입니다.