C++로 구현하는 이진 트리 노드의 전위 선행자(Preorder Predecessor) 찾기

이 문제에서는 하나의 이진 트리(Binary Tree)와 특정 노드 값이 주어지며, 해당 노드의 전위 선행자(Preorder Predecessor)를 출력하는 것이 목표입니다.

핵심 개념 정리

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 2개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가질 수 있는 특수한 형태의 트리 자료구조입니다.

전위 순회(Preorder Traversal)

전위 순회는 트리의 노드를 탐색하는 방법 중 하나로, 루트 노드 → 왼쪽 자식 → 오른쪽 자식 순서로 방문합니다.

전위 선행자(Preorder Predecessor)

전위 선행자란 전위 순회 과정에서 주어진 노드 바로 앞에 방문되는 노드를 의미합니다.

문제 예시

입력: 1
출력: 9

해결 접근 방법

1. 단순한 방법(Naive Approach)

가장 직관적인 방법은 이진 트리 전체를 전위 순회하여 순회 결과를 저장한 뒤, 그 목록에서 주어진 노드 바로 앞에 위치한 원소를 출력하는 것입니다. 하지만 이 방법은 트리 전체를 순회해야 하므로 시간과 공간 측면에서 비효율적입니다.

2. 효율적인 방법(Optimal Approach)

더 효율적인 해법은 부모 포인터를 활용해 노드의 위치를 기준으로 선행자를 찾는 것입니다. 규칙은 다음과 같습니다.

주어진 노드가 루트 노드인 경우: 전위 순회에서 가장 먼저 방문되므로 선행자가 없습니다. NULL을 반환합니다.
주어진 노드가 부모의 왼쪽 자식이거나, 부모에게 왼쪽 자식이 없는 경우: 전위 순회에서 루트 다음으로 왼쪽 서브트리를 방문하므로, 부모 노드가 곧 선행자입니다.
주어진 노드가 부모의 오른쪽 자식이고 부모에게 왼쪽 자식이 있는 경우: 부모의 왼쪽 서브트리에서 가장 마지막에 방문되는 노드가 선행자가 됩니다. 따라서 부모의 왼쪽 자식에서 시작해 오른쪽 자식을 계속 따라 내려간 노드가 선행자입니다.

C++ 구현 코드

#include <iostream>
using namespace std;
struct Node {
    struct Node *left, *right, *parent;
    int key;
};
struct Node* insertNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
    if (n == root)
        return NULL;
    Node* parent = n->parent;
    if (parent->left == NULL || parent->left == n)
        return parent;
    Node* curr = parent->left;
    while (curr->right != NULL)
        curr = curr->right;
    return curr;
}
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* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
    if (preOrderPredecessor)
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
    else
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
    return 0;
}

실행 결과

Preorder Predecessor of 50 is 18

동작 설명

위 예제에서 노드 50은 루트(99)의 왼쪽 자식(4)의 오른쪽 자식입니다. 부모 노드 4에는 왼쪽 자식 18이 존재하므로, 왼쪽 서브트리에서 가장 마지막에 방문되는 노드를 찾아야 합니다. 노드 18은 오른쪽 자식이 없으므로 그대로 선행자가 되어 결과적으로 50의 전위 선행자는 18이 됩니다.

시간 복잡도

이 알고리즘은 최악의 경우 한쪽 서브트리의 높이만큼만 탐색하므로 O(h)(h는 트리의 높이)의 시간 복잡도를 가지며, 전체 순회가 필요한 O(n) 방식보다 효율적입니다.