C++ 이진 트리에서 주어진 노드의 사촌(Cousin) 노드 출력하기

이진 트리(Binary Tree)란?

이진 트리는 모든 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 트리 자료구조입니다. 즉, 각 노드는 리프 노드이거나 하나 또는 두 개의 자식 노드를 갖습니다.

예시:

문제 정의

이 문제에서는 하나의 이진 트리와 트리 내의 특정 노드가 주어지며, 해당 노드의 사촌(cousin) 노드를 찾아 출력해야 합니다. 단, 형제(sibling) 노드는 출력 대상에서 제외합니다.

예를 들어 아래와 같은 이진 트리가 있다고 가정해 보겠습니다.

C++ 이진 트리에서 주어진 노드의 사촌(Cousin) 노드 출력하기

위 이진 트리에서 찾고자 하는 노드의 사촌 노드는 5입니다.

사촌 노드란?

개념을 더 명확히 하기 위해 사촌 노드를 정의해 보겠습니다. 이진 트리에서 두 노드가 동일한 레벨(깊이)에 위치하면서 서로 다른 부모 노드를 가질 때, 이 두 노드를 사촌 노드라고 합니다.

접근 방법

이제 이 문제의 해결 방법을 살펴보겠습니다.

핵심은 주어진 노드와 같은 레벨에 있는 모든 노드, 즉 루트 노드로부터 같은 거리에 있는 노드들을 출력하되, 주어진 노드 자신과 같은 부모를 공유하는 형제 노드는 제외하는 것입니다.

이를 위해 다음과 같은 순서로 진행합니다.

재귀 함수를 이용해 목표 노드가 위치한 레벨을 먼저 구합니다.
그다음 해당 레벨의 노드들을 순회하면서, 목표 노드 자신과 형제 노드를 제외한 나머지 노드를 출력합니다.

이 알고리즘의 시간 복잡도는 트리의 노드 수를 n이라 할 때 O(n)입니다.

C++ 구현 예제

위 로직을 바탕으로 작성한 C++ 프로그램은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node *left, *right;
};
Node *newNode(int item){
    Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
int levelOfNode(Node *root, Node *node, int level){
    if (root == NULL)
        return 0;
    if (root == node)
        return level;
    int downlevel = levelOfNode(root->left, node, level + 1);
    if (downlevel != 0)
        return downlevel;
    return levelOfNode(root->right, node, level + 1);
}
void printCousin(Node* root, Node *node, int level){
    if (root == NULL || level < 2)
        return;
    if (level == 2){
        if (root->left == node || root->right == node)
            return;
        if (root->left)
            cout << root->left->data << " ";
        if (root->right)
            cout << root->right->data;
    }
    else if (level > 2){
        printCousin(root->left, node, level - 1);
        printCousin(root->right, node, level - 1);
    }
}
void cousinNode(Node *root, Node *node){
    int level = levelOfNode(root, node, 1);
    printCousin(root, node, level);
}
int main(){
    Node *root = newNode(11);
    root->left = newNode(15);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(7);
    root->left->right->right = newNode(9);
    root->right->left = newNode(17);
    root->right->right = newNode(8);
    root->right->left->right = newNode(5);
    cout << "The cousin nodes are : ";
    cousinNode(root, root->right->right);
    return 0;
}

코드 설명

levelOfNode(): 루트부터 시작해 재귀적으로 탐색하며 목표 노드가 속한 레벨을 반환합니다.
printCousin(): 목표 노드의 부모를 만나면 그 자식들(목표 노드와 형제 노드)을 건너뛰고, 같은 레벨에 있는 다른 노드들만 출력합니다.
cousinNode(): 위 두 함수를 호출하여 전체 과정을 수행합니다.

실행 결과

The cousin nodes are : 3 7

위 예제에서 노드 8의 사촌 노드는 같은 레벨에 위치하지만 서로 다른 부모를 가진 3과 7임을 확인할 수 있습니다.