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

이 문제에서는 하나의 이진 트리(Binary Tree)와 정수 N이 주어지며, 이진 트리를 중위 순회(Inorder Traversal)했을 때 N번째에 방문하게 되는 노드를 찾아야 합니다.

이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 갖는 트리 구조입니다. 또한 순회(Traversal)란 트리의 모든 노드를 한 번씩 방문하는 과정을 의미하며, 필요에 따라 방문한 노드의 값을 출력하기도 합니다.

문제 예시

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

입력

N = 6

출력

3

설명

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

중위 순회 순서에서 6번째로 방문하는 노드의 값은 3입니다.

해결 접근 방법

핵심 아이디어는 재귀 호출(Recursive Call)을 이용한 중위 순회입니다. 중위 순회는 다음 순서로 진행됩니다.

1. 왼쪽 서브트리를 먼저 순회
2. 현재(루트) 노드 방문
3. 오른쪽 서브트리 순회

순회 과정에서 방문한 노드의 개수를 카운트하며, 카운트가 N과 일치하는 시점의 노드 값을 출력하면 됩니다. 이렇게 하면 전체 트리를 순회하면서 원하는 번째의 노드를 정확히 찾아낼 수 있습니다.

C++ 구현 코드

아래는 위 해결 방법을 실제로 구현한 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 findInOrderTraversalRec(struct Node* node, int N){
    static int count = 0;
    if (node == NULL)
        return;
    if (count <= N) {
        findInOrderTraversalRec(node->left, N); // 왼쪽 서브트리 순회
        count++;
        if (count == N)
            cout << node->data;  // N번째 노드 출력
        findInOrderTraversalRec(node->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 inorder traversal is ";
    findInOrderTraversalRec(root, N);
    return 0;
}

실행 결과

6th node in inorder traversal is 3

코드 설명

findInOrderTraversalRec() 함수는 재귀적으로 동작하며, static 변수 count를 사용해 지금까지 방문한 노드의 개수를 추적합니다. 왼쪽 자식 → 현재 노드 → 오른쪽 자식 순서로 탐색하면서 카운트를 증가시키고, 카운트가 N에 도달한 순간 해당 노드의 데이터를 출력합니다.

이 알고리즘의 시간 복잡도는 O(N)으로, 트리의 모든 노드를 한 번씩 방문하므로 노드 개수에 비례합니다. 공간 복잡도는 재귀 호출 스택 깊이에 따라 최악의 경우 O(H)(H는 트리의 높이)입니다.