C++로 이진 트리의 최대 너비 구하기

문제 설명

이진 트리가 주어졌을 때, 해당 트리의 최대 너비(maximum width)를 구하는 함수를 작성하는 것이 목표입니다. 여기서 트리의 너비란 각 레벨(깊이)에 존재하는 노드의 개수를 의미하며, 트리의 최대 너비는 모든 레벨의 너비 중 가장 큰 값으로 정의됩니다.

다음 트리를 예로 들어 살펴보겠습니다.

레벨 1의 너비: 1
레벨 2의 너비: 2
레벨 3의 너비: 3
레벨 4의 너비: 2

각 레벨의 너비를 비교해 보면 레벨 3의 너비가 가장 크므로, 위 트리의 최대 너비는 3입니다.

알고리즘

레벨 순회(level order traversal) 방식을 활용하면 문제를 효과적으로 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

재귀 호출을 통해 트리의 전체 높이(height)를 먼저 계산합니다.
1부터 높이까지 각 레벨마다 getWidth 함수를 호출하여 해당 레벨에 속한 노드의 개수를 구합니다.
각 레벨의 너비를 기존 최댓값과 비교하여 갱신한 후, 최종적으로 최대 너비를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
struct node {
    public:
        int data;
        node* left;
        node* right;
};
int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);
int getMaxWidth(node* root){
    int maxWidth = 0;
    int width;
    int h = height(root);
    int i;
    for (i = 1; i <= h; ++i) {
        width = getWidth(root, i);
        if (width > maxWidth) {
            maxWidth = width;
        }
    }
    return maxWidth;
}
int getWidth(node* root, int level){
    if (root == NULL) {
        return 0;
    }
    if (level == 1) {
        return 1;
    }
    else if (level > 1) {
        return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
    }
}
int height(node* node){
    if (node == NULL) {
        return 0;
    }
    int lHeight = height(node->left);
    int rHeight = height(node->right);
    return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}
node* newNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}
int main(){
    node *root = newNode(10);
    root->left = newNode(7);
    root->right = newNode(4);
    root->left->left = newNode(9);
    root->left->right = newNode(2);
    root->right->right = newNode(1);
    root->right->right->left = newNode(2);
    root->right->right->right = newNode(5);
    cout<<"Maximum width = " << getMaxWidth(root) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Maximum width = 3

복잡도 분석

이 구현은 각 레벨마다 트리를 다시 순회하므로, 최악의 경우 시간 복잡도는 O(n²)(n은 노드의 개수)가 됩니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 O(h)(h는 트리의 높이)입니다. 더 나은 성능이 필요하다면 큐(queue)를 활용한 BFS 순회를 사용하면 한 번의 순회, 즉 O(n) 시간 안에 최대 너비를 구할 수 있습니다.