C++로 이진 트리 전위 순회(Preorder)에서 N번째 노드 찾기

이 문제에서는 이진 트리(binary tree)와 정수 N이 주어지며, 전위 순회(Preorder Traversal) 과정에서 N번째로 방문하는 노드를 찾아 출력하는 것이 목표입니다.

이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 가진 트리 구조입니다.

순회(Traversal)란 트리의 모든 노드를 체계적으로 방문하는 과정을 의미하며, 필요에 따라 각 노드의 값을 출력하기도 합니다. 전위 순회는 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 노드를 방문하는 방식입니다.

문제 이해를 위한 예시

입력

N = 6

출력

6

설명

트리의 전위 순회 결과 : 1, 2, 4, 5, 3, 6, 7

전위 순회 순서를 보면 여섯 번째로 방문하는 노드의 값은 6입니다. 따라서 출력값은 6이 됩니다.

해결 접근 방법

핵심 아이디어는 재귀 호출(recursive call)을 활용한 전위 순회를 수행하는 것입니다. 각 호출에서 먼저 루트 노드를 방문한 뒤, 왼쪽 서브트리에 대해 preOrder()를 호출하고, 이어서 오른쪽 서브트리에 대해 preOrder()를 호출합니다.

순회를 진행하는 동안 방문한 노드의 개수를 카운트하며, 카운트가 N과 일치하는 순간 해당 노드의 값을 출력하면 됩니다.

구현 코드

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

struct Node* createNode(int item){
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void findPreOrderTraversalRec(struct Node* root, int N){
    static int nodeCount = 0;
    if (root == NULL)
        return;
    if (nodeCount <= N) {
        nodeCount++;
        if (nodeCount == N)
            cout << root->data;
        findPreOrderTraversalRec(root->left, N);
        findPreOrderTraversalRec(root->right, N);
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    int N = 6;
    cout << N << "th node in preorder traversal is ";
    findPreOrderTraversalRec(root, N);
    return 0;
}

실행 결과

6th node in preorder traversal is 6

코드 설명

위 코드에서 findPreOrderTraversalRec() 함수는 재귀적으로 트리를 전위 순회하며, 정적 변수(static variable)인 nodeCount를 사용해 지금까지 방문한 노드의 개수를 추적합니다. 루트 노드를 방문할 때마다 카운트를 증가시키고, 카운트가 N에 도달하면 해당 노드의 데이터를 출력합니다. 이후 왼쪽과 오른쪽 자식 노드를 차례대로 재귀 호출하여 순회를 계속 진행합니다.

이 방식의 시간 복잡도는 O(N)으로, 트리의 모든 노드를 한 번씩만 방문하므로 매우 효율적입니다.