Traversal 방법 비교

트리 순회는 트리 구조의 모든 노드를 체계적으로 방문하는 프로세스이다.
각 순회 방법은 노드를 방문하는 순서가 다르며, 이는 다양한 응용 프로그램에서 서로 다른 목적으로 사용된다.

트리 순회 방법은 각기 다른 특성과 장단점을 가지고 있으며, 문제의 성격에 따라 적합한 순회 방법을 선택해야 한다.

중위 순회(Inorder): 정렬된 순서가 필요할 때 특히 이진 탐색 트리에서 유용하다.
전위 순회(Preorder): 트리의 구조를 복제하거나 직렬화할 때 효과적이다.
후위 순회(Postorder): 자식 노드를 먼저 처리해야 하는 경우, 특히 트리 삭제 작업에 적합하다.
레벨 순서 순회(Level Order): 레벨별 처리가 필요하거나 최단 경로 문제를 해결할 때 유용하다.

각 순회 방법의 구현은 재귀적 접근법과 반복적 접근법 모두 가능하지만, 복잡성과 효율성 측면에서 차이가 있다. 재귀적 접근법은 구현이 간단하지만 깊은 트리에서는 스택 오버플로우가 발생할 수 있다. 반복적 접근법은 더 복잡한 구현이 필요하지만 메모리 효율성이 높다.

트리 순회의 주요 유형

트리 순회는 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search) 두 가지 방식으로 나뉜다.

깊이 우선 탐색(DFS, Depth-First Search) 기반 순회

DFS 기반의 순회 방식은 트리의 깊이를 우선적으로 탐색하는 방식으로 다음과 같은 3가지 유형이 있다.

순회 유형	방문 순서	탐색 원리
전위 순회 (Preorder Traversal)	루트 → 왼쪽 → 오른쪽	루트를 가장 먼저 방문
중위 순회 (Inorder Traversal)	왼쪽 → 루트 → 오른쪽	이진 탐색 트리(BST)에서 정렬된 순서로 방문
후위 순회 (Postorder Traversal)	왼쪽 → 오른쪽 → 루트	하위 노드를 모두 방문한 후 루트를 방문

재귀(Recursion) 또는 스택(Stack)을 사용하여 구현 가능

너비 우선 탐색(BFS, Breadth-First Search) 기반 순회

BFS 기반의 순회 방식은 트리의 레벨(층)을 순차적으로 탐색하는 방식으로, 레벨 순회(Level Order Traversal) 가 대표적이다.

순회 유형	방문 순서	탐색 원리
레벨 순회 (Level Order Traversal)	층(Level)별로 왼쪽에서 오른쪽으로 순회	큐(Queue)를 사용하여 한 레벨씩 방문

큐(Queue)를 사용하여 구현

트리 순회 유형별 예제

다음과 같은 이진 트리를 가정해보면:
1 2 3 4 5
A / \ B C / \ \ D E F
각 순회 방법에 따라 방문 순서는 다음과 같다.

순회 유형	방문 순서
전위 순회 (Preorder)	`A → B → D → E → C → F`
중위 순회 (Inorder)	`D → B → E → A → C → F`
후위 순회 (Postorder)	`D → E → B → F → C → A`
레벨 순회 (Level Order)	`A → B → C → D → E → F`

다음과 같은 이진 트리를 예로 들어보면:
1 2 3 4 5 6 7
1 / \ 2 3 / \ \ 4 5 6 / 7
각 순회 방법의 결과는 다음과 같다:
- 중위 순회(Inorder): [4, 2, 7, 5, 1, 3, 6]
- 전위 순회(Preorder): [1, 2, 4, 5, 7, 3, 6]
- 후위 순회(Postorder): [4, 7, 5, 2, 6, 3, 1]
- 레벨 순서 순회(Level Order): [[1], [2, 3], [4, 5, 6], [7]]

트리 순회

전위 순회 (Preorder Traversal)

구조:
- 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
순서:
1. 현재 노드(루트)를 방문
2. 왼쪽 서브트리 탐색
3. 오른쪽 서브트리 탐색
특징:
- 트리의 구조를 그대로 유지하며 복사하거나, 연산자 우선순위가 없는 표현식 트리(Polish Notation)를 탐색할 때 사용됨
- DFS 방식으로 구현되며 재귀 또는 스택을 이용한 반복적 방법으로 구현 가능
예제 (다음과 같은 트리를 전위 순회한다고 가정)

전위 순회 결과:
A → B → D → E → C → F

Python 구현

1
2
3
4
5
6
def preorder_traversal(node):
    if node is None:
        return
    print(node.value, end=" ")
    preorder_traversal(node.left)
    preorder_traversal(node.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def preorder_traversal(root):
    result = []
    
    def preorder(node):
        if node:
            # 1. 현재 노드 방문
            result.append(node.val)
            # 2. 왼쪽 서브트리 방문
            preorder(node.left)
            # 3. 오른쪽 서브트리 방문
            preorder(node.right)
    
    preorder(root)
    return result

# 반복적(비재귀) 방식
def preorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        # 스택에서 노드를 꺼내고 방문
        node = stack.pop()
        result.append(node.val)
        
        # 오른쪽 자식을 먼저 스택에 넣어 왼쪽 자식이 먼저 처리되도록 함
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

전위 순회는 트리 구조를 복제하거나 직렬화할 때 특히 유용하다. 루트 노드가 먼저 방문되기 때문에, 트리의 구조를 먼저 설정한 후 자식 노드를 처리할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function preorderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        // 오른쪽 자식을 먼저 스택에 넣어 왼쪽이 먼저 처리되도록 함
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    
    return result;
}

전위 순회의 응용

트리 직렬화: 전위 순회 결과와 중위 순회 결과만 있으면 이진 트리를 완전히 재구성할 수 있다.
트리의 깊은 복사(Deep Copy): 전위 순회를 사용하여 트리의 구조를 그대로 복제할 수 있다.
접두사 표기법(Prefix Notation): 수식 트리에서 전위 순회는 접두사 표기법(폴란드 표기법)으로 수식을 표현한다.

중위 순회 (Inorder Traversal)

구조:
- 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
순서:
1. 왼쪽 서브트리 탐색
2. 현재 노드(루트) 방문
3. 오른쪽 서브트리 탐색
특징:
- 이진 탐색 트리(Binary Search Tree, BST) 에서 오름차순 정렬된 결과를 얻을 수 있음
- DFS 방식으로 구현되며 재귀 또는 스택을 이용한 반복적 방법으로 구현 가능
예제

중위 순회 결과:
D → B → E → A → C → F

Python 구현

1
2
3
4
5
6
def inorder_traversal(node):
    if node is None:
        return
    inorder_traversal(node.left)
    print(node.value, end=" ")
    inorder_traversal(node.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def inorder_traversal(root):
    result = []
    
    def inorder(node):
        if node:
            # 1. 왼쪽 서브트리 방문
            inorder(node.left)
            # 2. 현재 노드 방문
            result.append(node.val)
            # 3. 오른쪽 서브트리 방문
            inorder(node.right)
    
    inorder(root)
    return result

# 반복적(비재귀) 방식
def inorder_traversal_iterative(root):
    result = []
    stack = []
    current = root
    
    while current or stack:
        # 가장 왼쪽 노드까지 이동
        while current:
            stack.append(current)
            current = current.left
        
        # 스택에서 노드를 꺼내고 방문
        current = stack.pop()
        result.append(current.val)
        
        # 오른쪽 서브트리로 이동
        current = current.right
    
    return result

중위 순회는 이진 탐색 트리(BST)에서 특히 유용하다.
BST에서 중위 순회를 수행하면 노드가 오름차순으로 방문되는데, 이는 정렬된 배열이 필요할 때 유용하다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current || stack.length > 0) {
        // 왼쪽 끝까지 이동
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        // 스택에서 노드를 꺼내고 값 추가
        current = stack.pop();
        result.push(current.val);
        
        // 오른쪽으로 이동
        current = current.right;
    }
    
    return result;
}

중위 순회의 응용

이진 탐색 트리 검증: 중위 순회 결과가 정렬되어 있는지 확인하여 BST의 유효성을 검사할 수 있다.
모리스 순회(Morris Traversal): 추가 공간 사용 없이 O(1) 공간 복잡도로 중위 순회를 수행할 수 있는 고급 기법이다.
k번째 작은 요소 찾기: BST에서 중위 순회를 수행하며 k번째 노드를 찾을 수 있다.

후위 순회 (Postorder Traversal)

구조:
- 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
순서:
1. 왼쪽 서브트리 탐색
2. 오른쪽 서브트리 탐색
3. 현재 노드(루트) 방문
특징:
- 트리의 모든 자식 노드를 먼저 처리한 후 루트를 방문하는 구조
- 폴더 삭제, 수식 트리 계산(연산자 우선순위 적용) 등에 많이 사용
- DFS 방식으로 구현되며 재귀 또는 스택을 이용한 반복적 방법으로 구현 가능
예제

후위 순회 결과:
D → E → B → F → C → A

Python 구현

1
2
3
4
5
6
def postorder_traversal(node):
    if node is None:
        return
    postorder_traversal(node.left)
    postorder_traversal(node.right)
    print(node.value, end=" ")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def postorder_traversal(root):
    result = []
    
    def postorder(node):
        if node:
            # 1. 왼쪽 서브트리 방문
            postorder(node.left)
            # 2. 오른쪽 서브트리 방문
            postorder(node.right)
            # 3. 현재 노드 방문
            result.append(node.val)
    
    postorder(root)
    return result

# 반복적(비재귀) 방식
def postorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    visited = []  # 방문한 노드 저장
    
    while stack:
        current = stack[-1]  # 스택 최상단 노드 확인
        
        # 자식 노드가 없거나 이미 방문했다면 현재 노드 방문
        if (not current.left and not current.right) or \
           (current.left in visited and current.right in visited):
            node = stack.pop()
            visited.append(node)
            result.append(node.val)
        else:
            # 오른쪽 자식이 있다면 스택에 추가
            if current.right and current.right not in visited:
                stack.append(current.right)
            # 왼쪽 자식이 있다면 스택에 추가
            if current.left and current.left not in visited:
                stack.append(current.left)
    
    return result

후위 순회는 자식 노드를 모두 처리한 후에야 부모 노드를 처리한다.
이는 트리의 각 노드에서 수행된 작업의 결과를 부모 노드에서 사용해야 할 때 유용하다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function postorderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    const stack1 = [root];
    const stack2 = [];
    
    // 첫 번째 스택에서 노드를 꺼내 두 번째 스택에 넣음
    while (stack1.length > 0) {
        const node = stack1.pop();
        stack2.push(node);
        
        // 왼쪽 자식을 먼저 스택1에 넣어 오른쪽이 먼저 스택2에 들어가도록 함
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    
    // 두 번째 스택에서 노드를 꺼내 결과에 추가
    while (stack2.length > 0) {
        result.push(stack2.pop().val);
    }
    
    return result;
}

후위 순회의 응용

트리 삭제: 자식 노드를 먼저 제거한 후 부모 노드를 제거하는 방식으로 트리 전체를 안전하게 삭제할 수 있다.
수식 계산: 후위 표기법(역폴란드 표기법)으로 표현된 수식을 계산할 때 사용된다.
디렉토리 크기 계산: 파일 시스템에서 디렉토리의 총 크기를 계산할 때, 각 하위 디렉토리의 크기를 먼저 계산한 후 합산한다.

레벨 순회 (Level Order Traversal)

구조:
- 루트부터 시작하여 같은 레벨의 노드를 왼쪽에서 오른쪽으로 탐색
순서:
1. 루트 노드 방문
2. 첫 번째 레벨의 노드들 방문 (좌 → 우)
3. 두 번째 레벨의 노드들 방문 (좌 → 우)
4. 더 이상 노드가 없을 때까지 반복
특징:
- 큐(Queue)를 이용하여 구현
- 최단 경로 탐색, AI 탐색(미니맥스, 알파베타 가지치기) 등에 사용됨
예제

레벨 순회 결과:
A → B → C → D → E → F

Python 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from collections import deque

def level_order_traversal(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque

def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

레벨 순서 순회는 너비 우선 탐색(BFS)을 사용하여 레벨별로 노드를 방문한다. 이는 최단 경로 문제나 트리의 구조적 특성을 분석할 때 유용하다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function levelOrderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

레벨 순서 순회의 응용

최소 높이 트리: 트리를 레벨 순으로 구축하면 최소 높이를 보장할 수 있다.
트리의 너비 계산: 각 레벨의 노드 수를 세어 트리의 최대 너비를 찾을 수 있다.
지그재그 순회(Zigzag Traversal): 레벨 순회의 변형으로, 홀수 레벨에서는 왼쪽에서 오른쪽으로, 짝수 레벨에서는 오른쪽에서 왼쪽으로 순회한다.

트리 순회의 비교 분석

순회 유형	구조	순서	사용 목적	시간 복잡도	공간 복잡도	장점	단점
전위 순회 (Preorder)	DFS	루트 → 왼쪽 → 오른쪽	트리 복사, 표현식 변환	O(N)	O(N) (재귀)	루트를 먼저 방문하여 빠른 탐색 가능	정렬된 순서로 데이터를 가져올 수 없음
중위 순회 (Inorder)	DFS	왼쪽 → 루트 → 오른쪽	BST에서 정렬된 데이터 탐색	O(N)	O(N) (재귀)	BST에서 오름차순 정렬이 가능	이진 탐색 트리에만 적절
후위 순회 (Postorder)	DFS	왼쪽 → 오른쪽 → 루트	폴더 삭제, 수식 계산	O(N)	O(N) (재귀)	하위 구조를 먼저 처리하여 안정적인 삭제 가능	루트를 마지막에 방문하여 즉시 처리하기 어려움
레벨 순회 (Level Order)	BFS	층별로 탐색	최단 경로 탐색, AI 탐색	O(N)	O(N) (큐)	한 층씩 방문하여 직관적 탐색 가능	큐 사용으로 인해 메모리 사용량 증가