C++로 이진 트리에서 가장 깊은 노드 찾기: 알고리즘과 구현 방법

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 우리의 과제는 트리에서 가장 깊은 노드(Deepest Node)를 찾는 것입니다.

이진 트리는 데이터를 저장하기 위해 사용되는 특수한 자료구조입니다. 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 조건을 가지고 있습니다.

여기서 이진 트리의 가장 깊은 노드란 트리 내에서 최대 높이에 위치한 노드를 의미합니다.

문제 예시

예제를 통해 문제를 이해해 보겠습니다.

입력:

출력: 8

해결 접근 방법

이 문제를 해결하는 방법은 여러 가지가 있습니다. 기본 원리는 트리의 높이를 구하고, 해당 높이에 있는 마지막 노드까지 순회한 후 그 노드를 반환하는 것입니다. 모든 해법은 결국 이 원리를 기반으로 하며, 여기서는 대표적이고 최적화된 두 가지 방법을 소개하겠습니다.

방법 1: 중위 순회(Inorder Traversal) 활용

가장 단순한 방법은 트리를 중위 순회하면서 현재 레벨(level)을 추적하는 것입니다. 순회 중 현재 레벨이 지금까지의 최대 레벨(maxLevel)보다 크다면, 해당 노드를 가장 깊은 노드(deepestNode)로 갱신합니다. 트리의 모든 노드를 순회한 후 deepestNode를 반환하면 됩니다. 트리 순회에는 재귀(recursion)를 사용합니다.

구현 예제

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

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

void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode) {
    if (root != NULL) {
        findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
        if (currentLevel > maxLevel) {
            deepestNode = root->data;
            maxLevel = currentLevel;
        }
        findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
    }
}

int findDeepestNodeBT(Node *root) {
    int deepestNode = 0;
    int maxLevel = 0;
    findDeepestNodeRec(root, 0, maxLevel, deepestNode);
    return deepestNode;
}

int main() {
    Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);

    cout << "주어진 이진 트리의 가장 깊은 노드는 " << findDeepestNodeBT(root);
    return 0;
}

실행 결과

주어진 이진 트리의 가장 깊은 노드는 8

방법 2: 트리의 높이 계산 후 해당 레벨의 노드 반환

또 다른 접근 방식은 먼저 주어진 트리의 높이(height)를 계산하는 것입니다. 그런 다음, 트리를 순회하면서 높이와 같은 레벨에 위치한 노드를 찾아 출력하면 됩니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

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

int calcHeight(Node* root) {
    if (!root) return 0;
    int leftHt = calcHeight(root->left) + 1;
    int rightHt = calcHeight(root->right) + 1;
    return max(leftHt, rightHt);
}

void findDeepestNodeBT(Node* root, int levels) {
    if (!root) return;
    if (levels == 1)
        cout << root->data;
    else if (levels > 1) {
        findDeepestNodeBT(root->left, levels - 1);
        findDeepestNodeBT(root->right, levels - 1);
    }
}

int main() {
    Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);

    int maxHeight = calcHeight(root);
    cout << "이진 트리의 가장 깊은 노드는 ";
    findDeepestNodeBT(root, maxHeight);
    return 0;
}

실행 결과

이진 트리의 가장 깊은 노드는 8

정리

두 방법 모두 재귀를 기반으로 트리를 순회한다는 공통점이 있습니다. 첫 번째 방법은 한 번의 순회만으로 깊은 노드를 찾을 수 있어 코드가 간결하고, 두 번째 방법은 트리의 높이를 명시적으로 계산한 후 목표 레벨의 노드를 찾는 방식이라 개념적으로 직관적입니다. 상황에 따라 적절한 방법을 선택하여 사용하면 됩니다.