문제 개요
이진 트리가 주어졌을 때, 각 노드에 저장된 키(key)가 몇 번째 레벨에 속하는지 계산하여 출력하는 것이 이 글의 목표입니다. 루트(root) 노드는 레벨 1에서 시작하며, 한 단계 아래 자식 노드로 내려갈 때마다 레벨이 1씩 증가합니다.
다음과 같은 이진 트리를 예로 들어 보겠습니다.
10 → 레벨 1 3, 211 → 레벨 2 140, 162, 100, 146 → 레벨 3
특정 키가 입력으로 주어지면, 프로그램은 해당 키가 위치한 레벨을 출력해야 합니다.
입력 및 출력 예시
입력: 10 3 211 140 162 100 146 출력: 10의 레벨은 1 3의 레벨은 2 211의 레벨은 2 140의 레벨은 3 162의 레벨은 3 100의 레벨은 3 146의 레벨은 3
접근 방식: BFS(너비 우선 탐색)
각 노드의 레벨을 구하는 가장 직관적인 방법은 큐(queue)를 이용한 레벨 순회(Level Order Traversal)입니다. 핵심 아이디어는 다음과 같습니다.
- 큐에 <노드 포인터, 레벨> 형태의 쌍(pair)을 함께 저장합니다.
- 루트 노드를 레벨 1로 큐에 삽입합니다.
- 큐에서 노드를 꺼낼 때마다 해당 노드의 데이터와 레벨을 출력합니다.
- 자식 노드를 큐에 넣을 때는 부모의 레벨에 1을 더한 값을 함께 저장합니다.
이렇게 하면 트리를 위에서 아래로, 왼쪽에서 오른쪽으로 순회하면서 모든 노드의 레벨을 정확하게 알아낼 수 있습니다.
알고리즘
시작
1단계 → 노드 구조체를 생성한다
struct node
struct node *left, *right
int data
끝
2단계 → 노드를 생성하는 함수를 만든다
node* newnode(int data)
node *temp = new node
temp->data = data
temp->left = temp->right = NULL
return temp
3단계 → 노드의 레벨을 찾는 함수를 만든다
void levels(Node* root)
IF root == NULL
Return
끝
STL queue<pair<struct Node*, int>> que 생성
que.push({root, 1})
STL pair<struct Node*, int> par 생성
While !que.empty() 동안 반복
par = que.front()
que.pop()
par.first->data 와 par.second 를 출력
IF par.first->left 가 존재하면
que.push({par.first->left, par.second + 1})
END
IF par.first->right 가 존재하면
que.push({par.first->right, par.second + 1})
End
End
종료C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct Node{
int data;
struct Node *left, *right;
};
// 트리의 각 노드 레벨을 출력하는 함수
void levels(Node* root){
if (root==NULL)
return;
queue<pair<struct Node*, int> >que;
que.push({root, 1});
pair<struct Node*, int> par;
while (!que.empty()) {
par = que.front();
que.pop();
cout << "Level of " << par.first->data << " is " << par.second << "\n";
if (par.first->left)
que.push({ par.first->left, par.second + 1 });
if (par.first->right)
que.push({ par.first->right, par.second + 1 });
}
}
// 노드를 생성하고 트리를 구성하는 함수
Node* newnode(int data){
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main(){
Node* root = NULL;
// 노드를 생성한다
root = newnode(34);
root->left = newnode(12);
root->right = newnode(50);
root->left->left = newnode(11);
root->left->right = newnode(54);
levels(root);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Level of 34 is 1 Level of 12 is 2 Level of 50 is 2 Level of 11 is 3 Level of 54 is 3
복잡도 분석
- 시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(n) — 최악의 경우(완전 이진 트리) 큐에는 마지막 레벨의 노드들이 최대 n/2개까지 저장될 수 있습니다.
정리하면, 큐에 노드와 레벨 정보를 함께 담아 BFS로 순회하기만 하면 별도의 재귀나 추가 자료구조 없이도 이진 트리의 모든 노드 레벨을 손쉽게 출력할 수 있습니다.