C++로 이진 탐색 트리(BST)의 짝수 노드 모두 출력하는 방법

이 문제에서는 하나의 이진 탐색 트리(Binary Search Tree)가 주어지며, 우리의 과제는 이 트리에 포함된 모든 짝수 값을 가진 노드를 출력하는 것입니다.

이진 탐색 트리란?

이진 탐색 트리는 다음 조건을 만족하는 이진 트리입니다.

왼쪽 서브트리에는 항상 부모 노드보다 작은 값을 가진 노드들이 위치합니다.
오른쪽 서브트리에는 항상 부모 노드보다 큰 값을 가진 노드들이 위치합니다.
트리의 모든 노드는 위 두 규칙을 반드시 따라야 합니다.

이러한 구조 덕분에 이진 탐색 트리는 값의 검색, 삽입, 삭제를 효율적으로 수행할 수 있으며, 중위 순회(In-order Traversal)를 하면 노드 값이 오름차순으로 정렬된 순서로 얻어진다는 특징도 있습니다.

문제 예시

예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.

출력 결과 − 12 30 54 80

해결 접근 방법

이 문제를 해결하려면 트리의 모든 노드를 순회하면서 현재 노드의 값을 확인해야 합니다. 노드의 값이 짝수라면 해당 노드를 출력하고, 홀수라면 건너뛰면 됩니다.

여기서는 중위 순회(In-order Traversal) 방식을 사용합니다. 중위 순회는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 방문하기 때문에, 짝수 노드들이 정렬된 순서대로 출력된다는 장점이 있습니다.

순회 알고리즘은 다음과 같습니다.

현재 노드가 NULL이면 재귀 호출을 종료합니다.
먼저 왼쪽 서브트리를 재귀적으로 순회합니다.
현재 노드의 값이 2로 나누어 떨어지면(짝수) 출력합니다.
마지막으로 오른쪽 서브트리를 재귀적으로 순회합니다.

C++ 구현 코드

아래 코드는 위에서 설명한 로직이 실제로 동작하는 모습을 보여줍니다.

#include <iostream>
using namespace std;

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

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

Node* insertNode(Node* node, int key){
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insertNode(node->left, key);
    else
        node->right = insertNode(node->right, key);
    return node;
}

void printEvenNode(Node* root){
    if (root != NULL) {
        printEvenNode(root->left);
        if (root->key % 2 == 0)
            cout<<root->key<<"\t";
        printEvenNode(root->right);
    }
}

int main(){
    Node* root = NULL;
    root = insertNode(root, 54);
    root = insertNode(root, 43);
    root = insertNode(root, 12);
    root = insertNode(root, 30);
    root = insertNode(root, 89);
    root = insertNode(root, 67);
    root = insertNode(root, 80);
    cout<<"All even nodes of the tree are :\n";
    printEvenNode(root);
    return 0;
}

코드 설명

newNode(): 새로운 노드를 생성하고 초기화하는 함수입니다.
insertNode(): BST의 규칙에 맞게 새 키 값을 삽입하는 함수입니다. 삽입할 값이 현재 노드보다 작으면 왼쪽으로, 그렇지 않으면 오른쪽으로 이동합니다.
printEvenNode(): 중위 순회를 수행하면서 짝수인 노드만 화면에 출력하는 핵심 함수입니다.

실행 결과

All even nodes of the tree are :
12 30 54 80

복잡도 분석

시간 복잡도: O(N) — 트리의 모든 노드를 한 번씩 방문해야 하므로 노드 개수 N에 비례합니다.
공간 복잡도: O(H) — 재귀 호출 스택이 트리의 높이 H만큼 사용됩니다.

이처럼 간단한 트리 순회와 조건 검사만으로 이진 탐색 트리의 모든 짝수 노드를 손쉽게 찾아 출력할 수 있습니다.