C++로 이진 트리가 레벨별로 정렬되어 있는지 확인하는 방법

이 글에서는 이진 트리(Binary Tree)가 레벨별로 정렬되어 있는지 확인하는 방법을 알아보겠습니다. 레벨별로 정렬된 이진 트리는 아래와 같은 구조를 가집니다.

위 트리처럼 각 레벨에서 노드들은 왼쪽에서 오른쪽으로 정렬되어 있으며, 동시에 각 레벨에 속한 값들이 이전 레벨의 값들보다 항상 커야 합니다.

문제 해결 접근 방식

이 문제는 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 큐(Queue)를 사용해 트리를 레벨 단위로 순회하면서, 현재 레벨에 속한 노드들의 최솟값(min_val)과 최댓값(max_val)을 추적합니다. 그리고 이전 레벨의 최댓값을 저장하는 prevMax 변수를 따로 유지합니다.

한 레벨의 순회가 끝날 때마다 현재 레벨의 최솟값이 이전 레벨의 최댓값(prevMax)보다 큰지 비교합니다. 만약 현재 레벨의 최솟값이 prevMax보다 작거나 같다면, 해당 트리는 레벨별로 정렬되어 있지 않으므로 즉시 false를 반환합니다. 반대로 조건을 만족한다면 prevMax를 현재 레벨의 최댓값으로 갱신한 뒤, 다음 레벨로 넘어가 같은 과정을 반복합니다. 모든 레벨을 통과하면 트리는 레벨별로 정렬된 것입니다.

C++ 구현 예제

#include <iostream>
#include <queue>
using namespace std;

class Node {
    public:
    int key;
    Node *left, *right;
};

Node* getNode(int key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

bool isLevelWiseSorted(Node* root) {
    int prevMax = INT_MIN;
    int min_val, max_val;
    int levelSize;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        // 현재 레벨에 있는 노드의 개수
        levelSize = q.size();
        min_val = INT_MAX;
        max_val = INT_MIN;

        // 현재 레벨의 모든 노드 처리
        while (levelSize > 0) {
            root = q.front();
            q.pop();
            levelSize--;

            min_val = min(min_val, root->key);
            max_val = max(max_val, root->key);

            if (root->left)
                q.push(root->left);
            if (root->right)
                q.push(root->right);
        }

        // 현재 레벨의 최솟값이 이전 레벨의 최댓값보다 작으면 정렬 실패
        if (min_val <= prevMax)
            return false;

        prevMax = max_val;
    }
    return true;
}

int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);

    if (isLevelWiseSorted(root))
        cout << "Tree is levelwise Sorted";
    else
        cout << "Tree is Not levelwise sorted";
}

출력 결과

Tree is level wise Sorted

코드 설명

getNode(): 새로운 노드를 동적으로 생성하고 key 값을 설정한 뒤, 좌우 자식 포인터를 NULL로 초기화하는 헬퍼 함수입니다.
isLevelWiseSorted(): 큐를 이용해 레벨 순서 순회를 수행하는 핵심 함수입니다. levelSize를 통해 현재 레벨의 노드 수를 파악하고, 해당 레벨 전체를 처리한 후 prevMax와 비교합니다.
main(): 1부터 7까지의 값을 가지는 샘플 이진 트리를 구성하고, 검증 결과를 출력합니다.

복잡도 분석

시간 복잡도: 모든 노드를 한 번씩 방문하므로 O(N)입니다. 여기서 N은 트리의 전체 노드 개수입니다.
공간 복잡도: 큐에는 최대 한 레벨의 노드가 저장되므로, 일반적인 경우 O(W)(W는 트리의 최대 폭), 최악의 경우 O(N)입니다.

이처럼 레벨 순서 순회와 최솟값·최댓값 비교만으로도 추가적인 자료구조 없이 간단하게 이진 트리의 레벨별 정렬 여부를 판별할 수 있습니다.