C++로 이진 트리 노드의 전위 순회 후속자(Preorder Successor) 찾기

문제 소개

이 문제에서는 하나의 이진 트리(binary tree)와 특정 노드의 값이 주어지며, 해당 노드의 전위 순회 후속자(preorder successor)를 출력하는 것이 목표입니다.

기본 개념 정리

이진 트리(Binary Tree): 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 트리 구조입니다.

전위 순회(Preorder Traversal): 루트 노드를 가장 먼저 방문하고, 그다음 왼쪽 자식, 마지막으로 오른쪽 자식을 방문하는 트리 순회 방식입니다.

전위 순회 후속자(Preorder Successor): 전위 순회 결과에서 해당 노드 바로 다음에 등장하는 노드를 의미합니다.

예시로 이해하기

입력: 9
출력: 0
설명: 트리의 전위 순회 결과는 5 9 0 1 2 5 입니다.
따라서 9의 전위 순회 후속자는 0입니다.

해결 접근 방법

방법 1: 전체 순회 후 찾기 (단순한 방법)

가장 직관적인 방법은 이진 트리의 전체 전위 순회 결과를 구한 뒤, 주어진 값 바로 뒤에 오는 원소를 출력하는 것입니다. 구현은 간단하지만 트리의 모든 노드를 순회해야 하므로 효율성이 떨어집니다.

방법 2: 노드의 위치를 활용한 효율적인 방법

더 효과적인 해법은 주어진 노드의 위치를 확인하고, 그 위치에 따라 후속자를 바로 찾아내는 것입니다. 전위 순회의 방문 순서(루트 → 왼쪽 → 오른쪽)를 고려하면 다음 규칙이 성립합니다.

• 왼쪽 자식이 있는 경우: 왼쪽 자식이 곧 전위 순회 후속자입니다.
• 왼쪽 자식은 없지만 오른쪽 자식이 있는 경우: 오른쪽 자식이 후속자입니다.
• 잎 노드(leaf node)이면서 왼쪽 자식인 경우: 형제 노드, 즉 부모의 오른쪽 자식이 후속자입니다.
• 잎 노드이면서 오른쪽 자식인 경우: 자신이 왼쪽 자식인 조상 노드를 찾아 계속 위로 올라간 뒤, 그 조상의 오른쪽 자식이 후속자입니다. 만약 그런 조상이 없다면 후속자는 존재하지 않습니다(NULL).

이 방식의 시간 복잡도는 트리의 높이에 비례하는 O(h)로, 전체 순회 방식(O(n))보다 훨씬 효율적입니다.

C++ 구현 예제

아래 프로그램은 부모 포인터(parent pointer)를 활용해 위 규칙을 구현한 예제입니다.

#include <iostream>
using namespace std;

struct Node {
    struct Node *left, *right, *parent;
    int key;
};

Node* insertNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}

Node* preOrderSuccessorNode(Node* root, Node* n){
    // 규칙 1: 왼쪽 자식이 있으면 그것이 후속자
    if (n->left)
        return n->left;
    // 규칙 2: 왼쪽 자식이 없고 오른쪽 자식만 있으면 오른쪽 자식이 후속자
    if (n->right)
        return n->right;
    // 규칙 3: 잎 노드인 경우, 자신이 왼쪽 자식인 조상을 찾아 올라감
    Node *curr = n, *parent = curr->parent;
    while (parent != NULL && parent->right == curr) {
        curr = curr->parent;
        parent = parent->parent;
    }
    if (parent == NULL)
        return NULL;
    return parent->right;
}

int main(){
    Node* root = insertNode(99);
    root->parent = NULL;
    root->left = insertNode(4);
    root->left->parent = root;
    root->left->left = insertNode(18);
    root->left->left->parent = root->left;
    root->left->right = insertNode(50);
    root->left->right->parent = root->left;
    root->right = insertNode(26);
    root->right->parent = root;
    root->right->left = insertNode(5);
    root->right->left->parent = root->right;
    root->right->right = insertNode(10);
    root->right->right->parent = root->right;

    Node* preOrder = preOrderSuccessorNode(root, root->left->right);
    if (preOrder) {
        cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
    } else {
        cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
    }
    return 0;
}

실행 결과

Preorder successor of 50 is 26

결과 분석

예제 트리의 전위 순회 결과는 99 4 18 50 26 5 10 입니다. 노드 50은 잎 노드이면서 부모(4)의 오른쪽 자식이므로, 자신이 왼쪽 자식인 조상인 루트(99)까지 올라간 뒤 루트의 오른쪽 자식인 26이 후속자로 반환됩니다. 이처럼 노드의 구조적 위치만 파악하면 전체 트리를 순회하지 않고도 전위 순회 후속자를 빠르게 구할 수 있습니다.