binary tree란 무엇이며, 흔한 순회 순서에는 어떤 것이 있나요?

Question

Accepted Answer

**binary tree(이진 트리)**는 각 **노드**가 최대 **두 개의 자식**(`left`와 `right`)을 갖는 계층 구조입니다. 단일 **루트(root)**를 가지며, 자식이 없는 노드는 **리프(leaf)**입니다. BST, heap, 수식 트리의 기반이 됩니다.

## 구조

```text
        1            깊이 0 (루트)
       / \
      2   3          깊이 1
     / \
    4   5            깊이 2 (리프: 4,5,3)
```

## 순회

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder(n):     # 왼쪽, 노드, 오른쪽 -> 4 2 5 1 3
    if n:
        inorder(n.left); print(n.val); inorder(n.right)

def preorder(n):    # 노드, 왼쪽, 오른쪽 -> 1 2 4 5 3
    if n:
        print(n.val); preorder(n.left); preorder(n.right)

def postorder(n):   # 왼쪽, 오른쪽, 노드 -> 4 5 2 3 1
    if n:
        postorder(n.left); postorder(n.right); print(n.val)
```

**level-order**(BFS) 순회는 queue를 사용하여 깊이 단위로 방문합니다.

| 순회 | 순서 | 흔한 용도 |
|---|---|---|
| Inorder | L, N, R | BST의 정렬된 출력 |
| Preorder | N, L, R | 트리 복사/직렬화 |
| Postorder | L, R, N | 트리 삭제, 수식 평가 |
| Level-order | 깊이 순 | BFS, 트리에서의 최단 경로 |

각 순회는 모든 노드를 한 번씩 방문 → **O(n)** 시간, 높이를 `h`라 할 때 **O(h)** 스택 공간.

## 왜 중요한가

binary tree는 자연스럽게 계층적인 데이터(파일 시스템, 파싱 트리, 의사결정 트리)를 모델링하며, 효율적인 검색과 정렬 구조의 근간을 이룹니다.

네 가지 순회를 익히는 것은 필수적입니다. 대부분의 tree 면접 문제는 이들 중 하나의 변형입니다.

순회	순서	흔한 용도
Inorder	L, N, R	BST의 정렬된 출력
Preorder	N, L, R	트리 복사/직렬화
Postorder	L, R, N	트리 삭제, 수식 평가
Level-order	깊이 순	BFS, 트리에서의 최단 경로