왼쪽 자식과 오른쪽 자식을 가진 이진 트리가 주어졌을 때, 그 트리의 가장 왼쪽과 가장 오른쪽에 위치한 노드를 출력하는 것이 이번 글의 목표입니다.
여기서 가장 왼쪽(leftmost) 노드란 트리에서 부모 노드를 기준으로 왼쪽에 연결된 노드를 의미하며, 가장 오른쪽(rightmost) 노드는 루트 노드를 기준으로 오른쪽에 연결된 노드를 의미합니다.
예시
입력: 106 20 320 100 21 61 52
출력: 106 20 320 100 52
알고리즘
핵심 아이디어는 레벨 순회(Level Order Traversal, BFS)입니다. 큐(queue)를 이용해 트리를 레벨별로 탐색하면서, 각 레벨에서 첫 번째 노드(i == 0)와 마지막 노드(i == n-1), 즉 양쪽 끝의 '코너' 노드만 결과 벡터에 저장합니다.
시작
Step 1 -> 노드 구조체 생성
int data 선언
struct node *left, *right 선언
Step 2 -> struct node* newNode(int val) 생성
node* temp = new node 생성
temp->data = val 설정
temp->left = temp->right = NULL 설정
return (temp)
Step 3 -> 함수 void print(node *root) 선언
IF root == NULL 이면
Return
STL queue<node*> que 사용
que.push(root) 호출
STL vector<int> ans 사용
While !que.empty() 동안 반복
int n = que.size()
for(int i = 0; i < n; i++) 반복
node *temp = que.front()
que.pop()
IF i == 0 이면
ans.push_back(temp->data)
ELSE IF i == n-1 이면
ans.push_back(temp->data)
IF temp->left 가 존재하면
que.push(temp->left)
IF temp->right 가 존재하면
que.push(temp->right)
For auto i : ans 반복
i 출력
Step 4 -> main() 에서
node *root = newNode(106) 로 노드 생성
print(root) 호출
종료
구현 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct node {
int data;
struct node* left, *right;
};
// 새로운 노드를 생성하는 함수
struct node* newNode(int val){
node* temp = new node;
temp->data = val;
temp->left = temp->right = NULL;
return (temp);
}
// 트리의 코너(양 끝) 요소를 출력하는 함수
void print(node *root) {
if(root == NULL)
return;
queue<node*> que;
que.push(root);
vector<int> ans;
while(!que.empty()){
int n = que.size();
for(int i = 0; i < n; i++){
node *temp = que.front();
que.pop();
if(i == 0)
ans.push_back(temp->data);
else if(i == n-1)
ans.push_back(temp->data);
if(temp->left)
que.push(temp->left);
if(temp->right)
que.push(temp->right);
}
}
for(auto i : ans)
cout << i << " ";
}
int main(){
node *root = newNode(106);
root->left = newNode(20);
root->right = newNode(320);
root->left->left = newNode(100);
root->left->right = newNode(21);
root->right->left = newNode(61);
root->right->right = newNode(52);
print(root);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
106 20 320 100 52
동작 원리 정리
위 코드는 큐를 활용한 너비 우선 탐색(BFS) 방식으로 동작합니다.
루트부터 시작해 한 레벨씩 내려가며, 각 레벨에 포함된 노드의 개수(n)를 먼저 파악합니다. 그다음 해당 레벨의 노드를 하나씩 꺼내면서 인덱스가 0인 노드(가장 왼쪽)와 인덱스가 n-1인 노드(가장 오른쪽)만 결과 벡터에 추가합니다. 만약 한 레벨에 노드가 하나뿐이라면 조건문 특성상 한 번만 저장되므로 중복 걱정은 없습니다.
이 방식의 시간 복잡도는 O(N)(N은 전체 노드 수), 공간 복잡도는 큐에 저장되는 최대 노드 수에 비례하여 O(W)(W는 트리의 최대 폭)입니다. 레벨 순회의 개념만 이해하고 있다면 재귀 없이도 간단하게 트리의 양 끝 노드를 추출할 수 있다는 점이 이 알고리즘의 가장 큰 장점입니다.