완전 이진 트리(Complete Binary Tree)란?
이진 트리가 하나 주어졌을 때, 이 트리가 완전 이진 트리인지 아닌지를 판별하는 프로그램을 만들어 보겠습니다.
완전 이진 트리는 다음 조건을 만족하는 트리입니다.
- 마지막 레벨을 제외한 모든 레벨이 노드로 가득 차 있어야 합니다.
- 마지막 레벨의 노드들은 가능한 한 왼쪽에 몰려 있어야 합니다.
예를 들어 아래와 같은 트리가 입력으로 주어지면, 모든 노드가 왼쪽부터 차례대로 채워져 있으므로 출력 결과는 True가 됩니다.
해결 전략: BFS(레벨 순회) 활용
이 문제는 큐(queue)를 이용한 너비 우선 탐색(BFS)으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 레벨 순서대로 노드를 방문하다가 처음으로 빈(null) 자리를 만나면, 그 이후에는 어떤 노드도 등장해서는 안 된다는 것입니다.
알고리즘 단계
- 양방향 큐(deque)를 하나 생성합니다.
- 루트 노드를 큐의 끝에 삽입합니다.
- 플래그(flag)를 False로 초기화합니다. (아직 빈 자리를 만나지 못했음을 의미)
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐의 왼쪽에서 요소를 꺼내 temp에 저장합니다.
- temp가 null이라면 → flag를 True로 설정합니다.
- flag가 이미 설정된 상태에서 temp가 null이 아니라면 → 완전 이진 트리가 아니므로 False를 반환합니다.
- 그 외의 경우 → temp의 왼쪽 자식과 오른쪽 자식을 큐 끝에 삽입합니다.
- 반복이 정상적으로 끝나면 True를 반환합니다.
Python 구현 예제
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):
q = deque()
q.append(root)
flag = False
while q:
temp = q.popleft()
if not temp:
flag = True
elif flag and temp:
return False
else:
q.append(temp.left)
q.append(temp.right)
return True
ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)
print(ob.solve(root))입력
root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8)
출력
True
동작 원리 살펴보기
위 예제 트리에서 BFS는 노드를 9 → 7 → 10 → 6 → 8 순서로 방문합니다. 이 과정에서 null 노드가 한 번도 등장하지 않았기 때문에 flag는 끝까지 False로 유지되며, 최종적으로 True가 반환됩니다.
반대로, 오른쪽 자식만 존재하고 왼쪽 자식이 비어 있는 노드가 있다면 큐에 null이 먼저 들어간 뒤 실제 노드가 뒤따르게 되고, 이 시점에 flag가 이미 True이므로 즉시 False가 반환됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(n) — 최악의 경우 큐에 트리의 한 레벨 전체(최대 n/2개 노드)가 저장될 수 있습니다.