Python으로 이진 트리의 특정 수직 레벨이 정렬되어 있는지 확인하는 방법

이진 트리가 하나 주어져 있다고 가정해 보겠습니다. 이때 해결해야 할 문제는 해당 트리의 특정 수직 레벨(vertical level)에 속한 노드들이 정렬되어 있는지 확인하는 것입니다. 여기서 수직 레벨이란, 왼쪽 자식 노드는 부모 노드보다 1 작은 레벨에, 오른쪽 자식 노드는 부모 노드보다 1 큰 레벨에 위치한다는 개념을 의미합니다. 만약 두 노드가 화면상 같은 위치에서 겹치더라도, 각 노드가 실제로 속한 레벨을 기준으로 정렬 여부를 판단하면 됩니다.

예를 들어 검사할 레벨이 l = -1일 때 다음과 같은 트리가 주어진다면,

레벨 -1에 해당하는 노드들의 값은 3과 7이며, 이 값들은 오름차순으로 정렬되어 있으므로 출력 결과는 True가 됩니다.

문제 해결 접근 방법

이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 큐(deque)를 사용해 트리를 순회하면서 각 노드의 수직 레벨을 함께 추적하고, 목표 레벨에 도달하는 노드들의 값을 순서대로 비교하는 방식입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• 루트 노드가 null이면 True를 반환합니다.
• previous_value를 음의 무한대(-inf)로 초기화합니다.
• current_level을 0으로 초기화합니다.
• current_node를 값이 0인 새로운 트리 노드로 초기화합니다.
• deque 타입의 큐 q를 하나 생성합니다.
• (root, 0) 쌍을 큐의 끝에 삽입합니다.
• 큐가 빌 때까지 다음 과정을 반복합니다.
  • current_node를 큐 맨 앞 요소의 첫 번째 값으로 설정합니다.
  • current_level을 큐 맨 앞 요소의 두 번째 값으로 설정합니다.
  • 큐에서 왼쪽 요소를 제거(popleft)합니다.
  • 만약 current_level이 목표 레벨과 같다면
    • previous_value <= current_node.val이면 previous_value를 현재 노드의 값으로 갱신합니다.
    • 그렇지 않으면 False를 반환합니다.
  • current_node.left가 null이 아니면 (current_node.left, current_level - 1)을 큐 끝에 삽입합니다.
  • current_node.right가 null이 아니면 (current_node.right, current_level + 1)을 큐 끝에 삽입합니다.
• 반복이 모두 끝나면 True를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 살펴보겠습니다.

from collections import deque
from sys import maxsize
INT_MIN = -maxsize
class TreeNode:
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None
def are_elements_sorted(root, level):
    if root is None:
        return True
    previous_value = INT_MIN
    current_level = 0
    current_node = TreeNode(0)
    q = deque()
    q.append((root, 0))
    while q:
        current_node = q[0][0]
        current_level = q[0][1]
        q.popleft()
        if current_level == level:
            if previous_value <= current_node.val:
                previous_value = current_node.val
            else:
                return False
        if current_node.left:
            q.append((current_node.left, current_level - 1))
        if current_node.right:
            q.append((current_node.right, current_level + 1))
    return True
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1
print(are_elements_sorted(root, level))

입력

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

출력

True

마무리

이 알고리즘은 BFS를 기반으로 하므로 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)입니다. 여기서 N은 트리의 전체 노드 개수입니다. 수직 레벨 개념은 이진 트리의 세로 방향 순회(vertical order traversal) 문제에서도 자주 활용되므로, 이번 예제를 통해 관련 개념을 함께 익혀두면 다양한 트리 문제를 해결할 때 큰 도움이 됩니다.