C++로 이진 트리에서 가장 큰 완전 이진 서브트리 찾기

개념

이 글에서는 주어진 이진 트리(Binary Tree) 안에서 가장 큰 완전 이진 서브트리(Complete Binary Sub-tree)의 크기를 찾는 방법을 다룹니다.

완전 이진 트리(Complete Binary Tree)란? 모든 레벨이 완전히 채워져 있고 마지막 레벨만 비어 있을 수 있으며, 마지막 레벨의 노드들은 최대한 왼쪽에 몰려 있는 이진 트리를 말합니다. 모든 포화 이진 트리(Perfect Binary Tree)는 반드시 완전 이진 트리이지만, 그 역은 성립하지 않습니다. 또한 어떤 트리가 완전 이진 트리가 아니라면 포화 이진 트리일 가능성도 없습니다.

입력 예시 1

      2
     / \
    3   4
   / \ / \
  5  6 7  8
 / \ /
9 10 11

출력

Size : 10
Inorder Traversal : 9 5 10 3 11 6 2 7 4 8
위 트리는 완전 이진 트리입니다.

입력 예시 2

      51
     / \
   31    61
   / \  / \
  6 21 46  71
 /
11

출력

Size : 4 (오른쪽 서브트리 기준)
Inorder Traversal : 11 46 61 71
위 트리는 완전 이진 트리가 아닙니다.

접근 방법

핵심 아이디어는 트리를 상향식(bottom-up)으로 방문하는 것입니다. 재귀 호출이 자식 노드에서 부모 노드로 되돌아올 때 서브트리에 대한 정보를 함께 전달하면, 부모 노드는 상수 시간(O(1)) 만에 자신이 완전 이진 트리인지 판별할 수 있습니다. 이때 좌우 서브트리는 자신이 포화(perfect)인지, 완전(complete)인지 부모에게 알려주어야 하며, 지금까지 발견한 가장 큰 완전 이진 트리의 크기도 함께 반환해야 합니다.

서브트리가 부모에게 전달해야 하는 정보를 정리하면 다음과 같습니다.

• 왼쪽 또는 오른쪽 자식 서브트리가 포화이면서 완전인지를 나타내는 bool 변수가 필요합니다.

• 재귀 호출 결과를 바탕으로 부모 서브트리가 완전 이진 트리인지 다음 세 가지 경우로 판단합니다.

  • 경우 A: 왼쪽 서브트리가 포화이고 오른쪽 서브트리가 완전이며 두 높이가 같다면, 현재 루트를 포함한 서브트리 역시 완전 이진 서브트리입니다. 크기는 좌우 서브트리 크기의 합에 1(현재 루트)을 더한 값입니다.

  • 경우 B: 왼쪽 서브트리가 완전이고 오른쪽 서브트리가 포화이며, 왼쪽 높이가 오른쪽보다 정확히 1 크다면 역시 완전 이진 서브트리입니다. 다만 이 경우 왼쪽 자식이 포화가 아니므로 루트 서브트리는 포화 이진 트리가 될 수 없습니다.

  • 경우 C: 위 조건에 해당하지 않으면 이 서브트리는 완전 이진 트리가 될 수 없으므로, 지금까지 좌우 서브트리에서 발견한 가장 큰 완전 서브트리를 그대로 반환합니다. 즉, 트리가 완전이 아니라면 포화도 아니라는 결론을 얻습니다.

구현 예제 (C++)

// 이 접근 방식의 C++ 구현
#include <bits/stdc++.h>
using namespace std;

// 트리 노드 구조체
struct node1 {
    int data;
    struct node1* left;
    struct node1* right;
};

// 새 노드를 생성하는 함수
struct node1* newNode(int data){
    struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
    node1->data = data;
    node1->left = NULL;
    node1->right = NULL;
    return node1;
};

// findCompleteBinaryTree 함수의 반환 타입 구조체
struct returnType {
    // 서브트리가 포화(perfect)인지 여부
    bool isPerfect;
    // 서브트리가 완전(complete)인지 여부
    bool isComplete;
    // 트리의 크기
    int size1;
    // 가장 큰 완전 서브트리의 루트
    node1* rootTree;
};

// 크기 값으로 트리의 높이를 계산하는 헬퍼 함수
int getHeight(int size1){
    return ceil(log2(size1 + 1));
}

// 가장 큰 완전 이진 서브트리를 찾아 반환하는 함수
returnType findCompleteBinaryTree(struct node1* root){
    returnType rt1;

    // 루트가 NULL이면 크기 0짜리 포화이자 완전인 트리로 간주
    if (root == NULL) {
        rt1.isPerfect = true;
        rt1.isComplete = true;
        rt1.size1 = 0;
        rt1.rootTree = NULL;
        return rt1;
    }

    // 왼쪽, 오른쪽 자식에 대한 재귀 호출
    returnType lv1 = findCompleteBinaryTree(root->left);
    returnType rv1 = findCompleteBinaryTree(root->right);

    // CASE - A : 왼쪽이 포화, 오른쪽이 완전, 높이 동일
    if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
        rt1.isComplete = true;
        // 오른쪽 서브트리가 포화라면 루트도 포화
        rt1.isPerfect = (rv1.isPerfect ? true : false);
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }

    // CASE - B : 왼쪽이 완전, 오른쪽이 포화, 왼쪽 높이가 1 더 큼
    if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
        rt1.isComplete = true;
        rt1.isPerfect = false;
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }

    // CASE - C : 완전 이진 트리가 될 수 없는 경우
    rt1.isPerfect = false;
    rt1.isComplete = false;
    rt1.size1 = max(lv1.size1, rv1.size1);
    rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree :
    rv1.rootTree);
    return rt1;
}

// 트리의 중위 순회(inorder traversal)를 출력하는 함수
void inorderPrint(node1* root){
    if (root != NULL) {
        inorderPrint(root->left);
        cout << root->data << " ";
        inorderPrint(root->right);
    }
}

// 드라이버 코드
int main(){
    // 트리 생성
    struct node1* root = newNode(50);
    root->left = newNode(30);
    root->right = newNode(60);
    root->left->left = newNode(5);
    root->left->right = newNode(20);
    root->right->left = newNode(45);
    root->right->right = newNode(70);
    root->right->left->left = newNode(10);

    // 가장 큰 완전 이진 서브트리 구하기
    struct returnType ans1 = findCompleteBinaryTree(root);
    cout << "Size : " << ans1.size1 << endl;

    // 찾은 서브트리의 중위 순회 출력
    cout << "Inorder Traversal : ";
    inorderPrint(ans1.rootTree);
    return 0;
}

실행 결과

Size : 4
Inorder Traversal : 10 45 60 70

복잡도 분석

각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다. 공간 복잡도는 재귀 호출 스택에 의해 트리의 높이에 비례하며, 편향된 트리의 최악의 경우 O(N)이 됩니다.