이진 트리 순회란?
이진 트리 순회(Binary Tree Traversal)는 트리의 모든 노드를 정해진 순서로 빠짐없이 한 번씩 방문하는 것입니다. 대표적으로 깊이 우선 계열의 전위·중위·후위 순회와, 너비 우선 계열의 레벨 순회가 있습니다.
핵심 한 줄: "세 가지 깊이 순회의 차이는 오직 루트를 언제 방문하느냐다." 왼쪽 자식과 오른쪽 자식은 항상 왼쪽 먼저, 루트의 위치만 앞·중간·뒤로 바뀝니다.
세 가지 깊이 순회 (DFS 계열)
| 순회 | 순서 | 활용 |
|---|---|---|
| 전위(Preorder) | 루트 → 왼 → 오 | 트리 복제, 식의 prefix 표기 |
| 중위(Inorder) | 왼 → 루트 → 오 | BST에서 오름차순 출력 |
| 후위(Postorder) | 왼 → 오 → 루트 | 트리 삭제, 식의 postfix 계산 |
이름의 "전/중/후"는 루트를 자식들에 대해 언제 방문하는지를 가리킵니다.
중위 순회와 BST
이진 탐색 트리(BST)는 "왼쪽 < 루트 < 오른쪽" 규칙을 지킵니다. 그래서 중위 순회(왼 → 루트 → 오)로 방문하면 값이 정확히 오름차순으로 나옵니다. BST에서 정렬된 출력이나 k번째 값을 찾을 때 바로 이 성질을 씁니다.
동작 원리
1단계. 현재 노드가 비어 있으면(null) 그냥 돌아옵니다(기저 사례).
2단계. 재귀로 세 동작을 수행합니다 — 왼쪽 자식 순회, 현재 노드 방문, 오른쪽 자식 순회.
3단계. 이 세 동작의 순서만 바꾸면 전위·중위·후위가 됩니다. 방문(visit)을 앞에 두면 전위, 가운데면 중위, 뒤면 후위.
레벨 순회는 다릅니다 — 큐를 써서 위에서 아래로, 같은 층은 왼쪽에서 오른쪽으로 방문합니다(BFS).
알고노트 시각화는 같은 트리를 순회 방식별로 어떤 순서로 방문하는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n) |
| 공간 | O(h) ~ O(n) |
노드를 한 번씩 보므로 O(n), 재귀 공간은 트리 높이 h만큼입니다(편향 트리면 O(n)).
예시로 따라가기
루트 2, 왼쪽 1, 오른쪽 3인 트리:
- •전위: 2, 1, 3
- •중위: 1, 2, 3 ← 오름차순(BST)
- •후위: 1, 3, 2
- •레벨: 2, 1, 3
자주 하는 실수
- •순서 혼동: 세 순회의 차이는 루트 위치뿐임을 기억하면 헷갈리지 않습니다.
- •중위=정렬을 잊음: BST에서 정렬 출력이 필요하면 따로 정렬하지 말고 중위 순회를 쓰세요.
- •빈 노드 처리: null 체크를 빼면 재귀가 터집니다.
알고노트에서 직접 확인하세요
같은 트리에서 전위·중위·후위·레벨 순회가 각각 어떤 순서로 노드를 방문하는지 알고노트에서 단계별로 확인할 수 있습니다.