문제 소개
이진 트리(Binary Tree)가 주어졌을 때, 그 안에서 가장 큰 완전 서브트리(Complete Subtree)의 크기를 구하는 것이 이번 글의 목표입니다. 여기서 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨이 노드로 가득 차 있고, 마지막 레벨의 노드들은 가능한 한 왼쪽에 치우쳐 배치된 이진 트리를 의미합니다.
예를 들어 다음과 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 정답은 크기 4이며, 해당 서브트리의 중위 순회(inorder traversal) 결과는 10, 45, 60, 70입니다.
알고리즘 접근 방식
이 문제는 후위 순회(post-order traversal) 방식으로 효율적으로 해결할 수 있습니다. 각 노드에서 왼쪽과 오른쪽 서브트리의 정보를 먼저 확인한 뒤, 현재 노드를 루트로 하는 서브트리가 완전 이진 트리인지 판단합니다. 이를 위해 다음 네 가지 값을 담는 반환 타입(returnType)을 정의합니다.
- isComplete: 현재 서브트리가 완전 이진 트리인지 여부 (초기값 False)
- isPerfect: 현재 서브트리가 포화 이진 트리(perfect binary tree)인지 여부 (초기값 False)
- size: 지금까지 발견된 가장 큰 완전 서브트리의 노드 개수 (초기값 0)
- rootTree: 가장 큰 완전 서브트리의 루트 노드 (초기값 None)
구체적인 처리 순서는 다음과 같습니다.
- 기저 조건: 루트가 null이면 isPerfect와 isComplete를 True로, size는 0, rootTree는 None으로 설정한 뒤 반환합니다.
- 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀적으로 checkCompleteness를 호출합니다.
- 경우 1: 왼쪽 서브트리가 포화(perfect)이고 오른쪽 서브트리가 완전(complete)이며 두 서브트리의 높이가 같다면, 현재 노드를 루트로 하는 전체 서브트리가 완전 이진 트리가 됩니다. 이때 isPerfect 값은 오른쪽 서브트리의 isPerfect를 따르며, size는 양쪽 size의 합에 1을 더한 값입니다.
- 경우 2: 왼쪽 서브트리가 완전(complete)이고 오른쪽 서브트리가 포화(perfect)이며, 왼쪽 높이가 오른쪽 높이보다 정확히 1만큼 크다면 현재 서브트리 역시 완전 이진 트리입니다. 단, 이 경우에는 포화 이진 트리가 아니므로 isPerfect는 False가 됩니다.
- 그 외의 경우: 현재 노드를 루트로 하는 서브트리는 완전 이진 트리가 될 수 없으므로, 왼쪽과 오른쪽 자식 중 더 큰 완전 서브트리를 최종 결과로 선택합니다.
Python 구현 코드
다음은 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
import math
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class returnType:
def __init__(self):
self.isPerfect = None
self.isComplete = None
self.size = 0
self.rootTree = None
def getHeight(size):
return int(math.ceil(math.log(size + 1) / math.log(2)))
def checkCompleteness(root):
ret_type = returnType()
# 기저 조건: 빈 트리는 포화이자 완전 이진 트리
if root is None:
ret_type.isPerfect = True
ret_type.isComplete = True
ret_type.size = 0
ret_type.rootTree = None
return ret_type
left_tree = checkCompleteness(root.left)
right_tree = checkCompleteness(root.right)
# 경우 1: 왼쪽은 포화, 오른쪽은 완전, 높이가 같은 경우
if (left_tree.isPerfect and right_tree.isComplete
and getHeight(left_tree.size) == getHeight(right_tree.size)):
ret_type.isComplete = True
ret_type.isPerfect = right_tree.isPerfect
ret_type.size = left_tree.size + right_tree.size + 1
ret_type.rootTree = root
return ret_type
# 경우 2: 왼쪽은 완전, 오른쪽은 포화, 왼쪽 높이가 1 더 큰 경우
if (left_tree.isComplete and right_tree.isPerfect
and getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
ret_type.isComplete = True
ret_type.isPerfect = False
ret_type.size = left_tree.size + right_tree.size + 1
ret_type.rootTree = root
return ret_type
# 그 외: 현재 서브트리는 완전 이진 트리가 될 수 없음
ret_type.isPerfect = False
ret_type.isComplete = False
ret_type.size = max(left_tree.size, right_tree.size)
if left_tree.size > right_tree.size:
ret_type.rootTree = left_tree.rootTree
else:
ret_type.rootTree = right_tree.rootTree
return ret_type
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)
ans = checkCompleteness(root)
print("Size:", ans.size)
print("Inorder Traversal: ", end='')
print_tree(ans.rootTree)
입력 예시
root = TreeNode(50) root.left = TreeNode(30) root.right = TreeNode(60) root.left.left = TreeNode(5) root.left.right = TreeNode(20) root.right.left = TreeNode(45) root.right.right = TreeNode(70) root.right.left.left = TreeNode(10)
실행 결과
Size: 4 Inorder Traversal: 10, 45, 60, 70,
복잡도 및 정리
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 재귀 호출 스택에 의해 결정되며, 균형 잡힌 트리에서는 O(log n), 편향된 트리에서는 최악의 경우 O(n)이 됩니다.
핵심은 각 노드가 "포화 여부", "완전 여부", "크기"라는 세 가지 상태 정보를 부모 노드에게 전달한다는 점입니다. 이처럼 후위 순회와 상태 추적을 결합하면 이진 트리의 구조적 성질을 활용하는 다양한 문제를 선형 시간 안에 깔끔하게 해결할 수 있습니다.