파이썬으로 주어진 이진 트리가 힙인지 판별하는 방법

문제 이해하기

이진 트리가 하나 주어졌을 때, 해당 트리가 힙(Heap)인지 아닌지를 판별해야 합니다. 힙이 되기 위해서는 다음과 같은 조건을 만족해야 합니다.

트리는 완전 이진 트리(Complete Binary Tree)여야 합니다. 즉, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 합니다.
모든 노드의 값은 자식 노드의 값보다 크거나 같아야 합니다. 이를 최대 힙(Max-Heap) 속성이라고 합니다.

예를 들어 다음과 같은 트리가 입력으로 주어지면, 출력은 True가 됩니다.

해결 접근 방법

이 문제는 세 가지 보조 함수를 재귀적으로 구현하여 해결할 수 있습니다.

1. 노드 개수 세기 — number_of_nodes()

루트가 null이면 0을 반환합니다.
그렇지 않으면 1 + 왼쪽 서브트리의 노드 수 + 오른쪽 서브트리의 노드 수를 반환합니다.

2. 힙 속성 검사 — has_heap_property()

왼쪽과 오른쪽 자식이 모두 없는 리프 노드라면 True를 반환합니다.
오른쪽 자식만 없다면, root.val >= root.left.val 인지를 반환합니다.
양쪽 자식이 모두 존재한다면, 부모 값이 두 자식 값보다 크거나 같은 경우에 한해 왼쪽과 오른쪽 서브트리에 대해 재귀적으로 검사를 계속합니다. 조건을 만족하지 않으면 False를 반환합니다.

3. 완전 트리 검사 — is_complete_tree()

루트가 null이면 True를 반환합니다.
현재 인덱스가 전체 노드 개수보다 크거나 같으면 False를 반환합니다. 이는 노드가 배열 기반 힙에서 기대되는 위치보다 뒤에 있다는 의미입니다.
그렇지 않으면 왼쪽 자식(인덱스 2*i+1)과 오른쪽 자식(인덱스 2*i+2)에 대해 재귀적으로 검사합니다.

4. 메인 로직

먼저 전체 노드 개수를 구합니다.
is_complete_tree()와 has_heap_property()가 모두 참이면 True, 그렇지 않으면 False를 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
    def number_of_nodes(self, root):
        if root is None:
            return 0
        else:
            return (1 + self.number_of_nodes(root.left) + self.number_of_nodes(root.right))
    def has_heap_property(self, root):
        if (root.left is None and root.right is None):
            return True
        if root.right is None:
            return root.val >= root.left.val
        else:
            if (root.val >= root.left.val and
                root.val >= root.right.val):
                return (self.has_heap_property(root.left) and self.has_heap_property(root.right))
            else:
                return False
    def is_complete_tree(self, root,index, node_count):
        if root is None:
            return True
        if index >= node_count:
            return False
        return (self.is_complete_tree(root.left, 2 * index + 1, node_count) and self.is_complete_tree(root.right, 2 * index + 2, node_count))
    def is_heap(self):
        node_count = self.number_of_nodes(self)
        if (self.is_complete_tree(self, 0, node_count) and self.has_heap_property(self)):
            return True
        else:
            return False
root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)
print(root.is_heap())

입력

root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)

출력

True

정리

이 방법은 트리를 순회하면서 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 완전 이진 트리 여부와 최대 힙 속성이라는 두 가지 조건을 독립적으로 검사한 후 결과를 결합하기 때문에 코드가 명확하고 이해하기 쉽습니다. 실제 면접이나 코딩 테스트에서 힙 관련 문제를 다룰 때 유용하게 활용할 수 있는 기본 패턴입니다.