C++로 이진 트리의 최대 깊이(높이) 구하는 프로그램 작성하기

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 우리의 과제는 해당 트리의 최대 깊이(Maximum Depth), 즉 높이(Height)를 구하는 프로그램을 작성하는 것입니다.

문제 이해하기

먼저 예시를 통해 문제를 살펴보겠습니다.

위 트리의 높이는 3입니다.

접근 방법: 재귀적 높이 계산

트리의 최대 높이를 구하려면 왼쪽 서브트리와 오른쪽 서브트리의 높이를 각각 확인한 뒤, 두 값 중 더 큰 값에 1을 더하면 됩니다. 여기서 더하는 1은 현재 노드(루트) 자신의 높이를 의미합니다.

이 과정은 재귀(Recursion)로 처리됩니다. 트리의 마지막 노드, 즉 리프 노드에 도달할 때까지 계속해서 하위 서브트리의 높이를 구하고, 거꾸로 올라오면서 1씩 더해 전체 트리의 높이를 계산하게 됩니다.

예시 풀이 과정

위 예시를 이 방법으로 단계별로 풀어보겠습니다.

트리 전체의 높이는 다음과 같이 정의됩니다.

height(3) = max(height(5), height(7)) + 1

이를 위해 값이 5와 7인 노드의 높이를 먼저 계산해야 합니다.

height(5) = max(height(1), height(9)) + 1
height(7) = 1 — 서브트리가 존재하지 않는 리프 노드이기 때문입니다.

마찬가지로 height(1) = height(9) = 1이므로,

height(5) = max(1, 1) + 1 = 2
height(3) = max(height(5), height(7)) + 1 = max(2, 1) + 1 = 3

따라서 트리의 최종 높이는 3이 됩니다.

C++ 구현 코드

위 해결 방법을 구현한 C++ 프로그램은 다음과 같습니다.

예제 코드

#include <iostream>
using namespace std;

class node {
    public:
    int data;
    node* left;
    node* right;
};

int height(node* node) {
    if (node == NULL)
        return 0;
    else {
        int lDepth = height(node->left);
        int rDepth = height(node->right);
        if (lDepth > rDepth)
            return(lDepth + 1);
        else
            return(rDepth + 1);
    }
}

node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}

int main() {
    node *root = insertNode(4);
    root->left = insertNode(5);
    root->right = insertNode(0);
    root->left->left = insertNode(1);
    root->left->right = insertNode(9);
    cout<<"The height of the given binary tree is "<<height(root);
    return 0;
}

실행 결과

The height of the given binary tree is 3

코드 동작 원리

height() 함수: 노드가 NULL이면 0을 반환하고, 그렇지 않으면 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 구한 뒤 더 큰 값에 1을 더해 반환합니다.
insertNode() 함수: 새로운 노드를 생성하고 데이터를 초기화한 후 반환하는 유틸리티 함수입니다.
main() 함수: 예시 트리를 구성한 뒤 height() 함수를 호출하여 결과를 출력합니다.

시간 복잡도

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 개수입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 따라 결정되며, 최악의 경우 트리의 높이 h만큼, 즉 O(h)입니다.