Python으로 이진 트리에서 가장 큰 포화 이진 하위 트리 찾기

이진 트리가 하나 주어졌을 때, 그 안에서 가장 큰 포화(perfect) 이진 하위 트리의 크기를 찾아야 합니다. 포화 이진 트리란 모든 내부 노드가 정확히 두 개의 자식을 가지며, 모든 리프 노드가 동일한 깊이(레벨)에 위치하는 이진 트리를 의미합니다.

예를 들어 입력 트리가 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 3이며, 찾아진 하위 트리는 다음과 같습니다.

Python으로 이진 트리에서 가장 큰 포화 이진 하위 트리 찾기

해결 접근 방법

이 문제는 후위 순회(post-order traversal) 방식의 재귀로 효율적으로 해결할 수 있습니다. 각 단계는 다음과 같습니다.

왼쪽·오른쪽 서브트리의 판정 결과를 저장할 RetType 클래스를 정의합니다. 이 클래스는 isPerfect(포화 여부), height(높이), rootTree(가장 큰 포화 서브트리의 루트) 세 가지 정보를 담으며, 초기값은 모두 0입니다.
get_perfect_subtree() 함수를 정의하고, 루트 노드를 인자로 전달합니다.
r_type := 새로운 RetType 객체를 생성합니다.
만약 root가 None이라면:
- r_type.isPerfect := True
- r_type.height := 0
- r_type.rootTree := None
- r_type을 반환합니다.
left_subtree := get_perfect_subtree(root.left)
right_subtree := get_perfect_subtree(root.right)
왼쪽 서브트리와 오른쪽 서브트리가 모두 포화 이진 트리이고, 두 서브트리의 높이가 같다면:
- r_type.height := 왼쪽 서브트리 높이 + 1
- r_type.isPerfect := True로 설정
- r_type.rootTree := 현재 root
- r_type을 반환합니다.
그렇지 않다면 r_type.isPerfect := False로 설정합니다.
r_type.height := 왼쪽 서브트리 높이와 오른쪽 서브트리 높이 중 최댓값
만약 왼쪽 서브트리의 높이가 더 크다면:
- r_type.rootTree := left_subtree.rootTree
그렇지 않다면:
- r_type.rootTree := right_subtree.rootTree
r_type을 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해할 수 있습니다.

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class RetType:
    def __init__(self):
        self.isPerfect = False
        self.height = 0
        self.rootTree = None

def get_perfect_subtree(root):
    r_type = RetType()
    if root == None:
        r_type.isPerfect = True
        r_type.height = 0
        r_type.rootTree = None
        return r_type

    left_subtree = get_perfect_subtree(root.left)
    right_subtree = get_perfect_subtree(root.right)

    if (left_subtree.isPerfect and right_subtree.isPerfect
            and left_subtree.height == right_subtree.height):
        r_type.height = left_subtree.height + 1
        r_type.isPerfect = True
        r_type.rootTree = root
        return r_type

    r_type.isPerfect = False
    r_type.height = max(left_subtree.height, right_subtree.height)
    if left_subtree.height > right_subtree.height:
        r_type.rootTree = left_subtree.rootTree
    else:
        r_type.rootTree = right_subtree.rootTree
    return r_type

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

res = get_perfect_subtree(root)
h = res.height

print("Size:", pow(2, h) - 1)
print("Tree:", end=" ")
print_tree(res.rootTree)

입력

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

출력

Size: 3
Tree: 5, 3, 6,

동작 원리 및 복잡도 분석

위 예제에서 노드 3을 루트로 하는 서브트리(자식 노드 5와 6)는 양쪽 자식이 모두 리프이므로 포화 이진 트리입니다. 이 서브트리의 높이는 1이므로 크기는 2² − 1 = 3이 됩니다. 반면 전체 트리의 루트인 노드 2는 오른쪽에 자식이 하나뿐이므로 포화 이진 트리가 될 수 없습니다.

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n), 재귀 호출 스택으로 인한 공간 복잡도는 트리의 높이에 비례하여 최악의 경우 O(n)입니다.