C++로 이진 트리에서 주어진 키의 오른쪽 다음 노드 찾기

이 문제에서는 하나의 이진 트리(BT)와 키(key) 값이 주어지며, 우리의 과제는 주어진 키의 오른쪽 다음 노드를 찾는 것입니다.

이진 트리(Binary Tree)는 데이터 저장을 위해 사용되는 대표적인 자료 구조로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식과 오른쪽 자식)를 가질 수 있는 구조입니다.

문제 이해를 위한 예시

다음과 같은 이진 트리가 있고, 찾고자 하는 키가 4라고 가정해 보겠습니다.

입력

key = 4

출력

5

설명

노드 4와 같은 레벨(깊이)에 있는 노드 중 바로 오른쪽에 위치한 요소는 5입니다. 따라서 결과값으로 5를 반환합니다.

해결 접근 방법

이 문제의 가장 간단하고 직관적인 해결 방법은 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS)을 활용하는 것입니다.

동작 원리는 다음과 같습니다.

1. 큐(queue)를 사용하여 트리를 레벨 단위로 순회합니다.
2. 각 노드와 함께 해당 노드의 레벨 정보를 함께 저장합니다.
3. 순회 중 주어진 키 값과 일치하는 노드를 발견하면, 큐에 저장된 다음 노드가 같은 레벨인지 확인합니다.
4. 같은 레벨의 노드가 존재하면 그 노드를 반환하고, 존재하지 않으면 NULL을 반환합니다.

구현 코드

#include <iostream>
#include <queue>
using namespace std;

struct node {
    struct node *left, *right;
    int key;
};

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

node* findNextRightNodeBT(node *root, int k) {
    if (root == NULL)
        return 0;
    queue<node *> nodeVal;
    queue<int> nodeLevel;
    int level = 0;
    nodeVal.push(root);
    nodeLevel.push(level);
    while (nodeVal.size()) {
        node *node = nodeVal.front();
        level = nodeLevel.front();
        nodeVal.pop();
        nodeLevel.pop();
        if (node->key == k) {
            if (nodeLevel.size() == 0 || nodeLevel.front() != level)
                return NULL;
            return nodeVal.front();
        }
        if (node->left != NULL) {
            nodeVal.push(node->left);
            nodeLevel.push(level+1);
        }
        if (node->right != NULL) {
            nodeVal.push(node->right);
            nodeLevel.push(level+1);
        }
    }
    return NULL;
}

int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);

    int key = 4;
    cout<<"노드 "<<key<<"의 오른쪽 다음 노드는 ";
    node *nextNode = findNextRightNodeBT(root, key);
    if(nextNode != NULL)
        cout<<nextNode->key;
    else
        cout<<"존재하지 않습니다";
    return 0;
}

실행 결과

노드 4의 오른쪽 다음 노드는 5

코드 설명

위 코드에서는 두 개의 큐를 사용합니다. 하나는 노드 자체를 저장하는 nodeVal이고, 다른 하나는 각 노드의 레벨을 저장하는 nodeLevel입니다. 두 큐는 항상 동기화되어 같은 인덱스에 대응됩니다.

키 값과 일치하는 노드를 찾으면, nodeLevel 큐의 맨 앞 값을 현재 레벨과 비교합니다. 두 값이 같다면 큐에 있는 다음 노드가 같은 레벨에 있다는 의미이므로 해당 노드를 반환하고, 큐가 비어 있거나 레벨이 다르면 NULL을 반환합니다.

시간 복잡도 분석

이 알고리즘은 트리의 모든 노드를 최악의 경우 한 번씩 방문하므로 시간 복잡도는 O(N)입니다(N은 노드의 개수). 공간 복잡도 역시 큐에 최대 한 레벨의 노드들을 저장하므로 O(N)입니다.