C++로 부모 포인터가 있는 이진 트리에서 오른쪽 형제 노드 찾기

이 문제에서는 부모 포인터(parent pointer)를 포함하는 이진 트리가 주어지며, 우리의 과제는 트리 내 특정 노드의 오른쪽 형제(right sibling) 노드를 찾는 것입니다.

문제 이해하기

예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력

Node = 3

출력

7

위 예시에서 값이 3인 노드의 오른쪽 형제는 동일한 레벨에 위치한 값이 7인 노드입니다.

해결 접근 방법

이 문제의 핵심은 현재 노드와 같은 레벨에 있으면서 가장 가까운 조상 노드(단, 현재 노드 자신과 그 부모 노드는 제외)를 찾는 것입니다. 구체적인 진행 과정은 다음과 같습니다.

1. 현재 노드에서 출발해 부모 포인터를 따라 위로 올라갑니다. 이때 현재 노드가 부모의 오른쪽 자식이거나, 부모의 오른쪽 자식이 없는 상태에서 왼쪽 자식이라면 계속 위로 올라가며 레벨 카운트를 1씩 증가시킵니다.
2. 오른쪽 서브트리가 존재하는 조상을 만나면, 해당 조상의 오른쪽 자식으로 이동합니다.
3. 저장해 둔 레벨 수만큼 아래로 내려갑니다(왼쪽 자식을 우선하며, 없으면 오른쪽 자식 사용). 목표 레벨에 도달한 노드가 바로 원하는 오른쪽 형제입니다.

이 방법은 트리의 높이에 비례하는 시간 복잡도 O(h)와 상수 공간 O(1)만으로 문제를 해결할 수 있어 매우 효율적입니다.

구현 예제

아래는 위 접근 방식을 C++로 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
    Node* temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    temp->parent = parent;
    return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
    if (node == NULL || node->parent == NULL)
        return NULL;
    while (node->parent->right == node ||
        (node->parent->right == NULL && node->parent->left == node)) {
            if (node->parent == NULL || node->parent->parent == NULL)
                return NULL;
        node = node->parent;
        level++;
    }
    node = node->parent->right;
    if (node == NULL)
        return NULL;
    while (level > 0) {
        if (node->left != NULL)
            node = node->left;
        else if (node->right != NULL)
            node = node->right;
        else
            break;
        level--;
    }
    if (level == 0)
        return node;
    return findRightSiblingNodeBT(node, level);
}
int main(){
    Node* root = newNode(4, NULL);
    root->left = newNode(2, root);
    root->right = newNode(5, root);
    root->left->left = newNode(1, root->left);
    root->left->left->left = newNode(9, root->left->left);
    root->left->left->left->left = newNode(3, root->left->left->left);
    root->right->right = newNode(8, root->right);
    root->right->right->right = newNode(0, root->right->right);
    root->right->right->right->right = newNode(7, root->right->right->right);
    Node * currentNode = root->left->left->left->left;
    cout<<"The current node is "<<currentNode->data<<endl;
    Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
    if (rightSibling)
        cout<<"The right sibling of the current node is "<<rightSibling->data;
    else
        cout<<"No right siblings found!";
    return 0;
}

실행 결과

The current node is 3
The right sibling of the current node is 7