중위, 전위, 후위 DFS
세 가지 DFS 순회를 모두 명시적 스택을 사용한 재귀 및 반복 방식으로 구현하고, 각 순서가 유용한 경우를 설명합니다.
중위, 전위, 후위 DFS은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
세 가지 DFS 순회 순서
이진 트리의 DFS는 루트를 자식에 비해 언제 처리하는지에 따라 세 가지 순서 중 하나로 노드를 방문합니다. 전위 순회: 루트 → 왼쪽 → 오른쪽. 중위 순회: 왼쪽 → 루트 → 오른쪽. 후위 순회: 왼쪽 → 오른쪽 → 루트. 이름만 보아도 순서에서 루트가 어디에 배치되는지 알 수 있습니다. 문제마다 요구하는 순서가 다르므로 세 가지를 모두 이해하는 것이 중요합니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')재귀 전위 순회
전위 순회에서는 현재 노드를 서브트리보다 먼저 처리합니다. 이는 트리를 위에서 아래로 자연스럽게 읽는 방식과 같으며, 트리 복사, 직렬화, 전위 표기식 평가에 사용됩니다. 재귀 구현은 매우 짧지만, 트리의 높이가 h일 때 깊이 O(h)의 호출 스택을 생성합니다.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]재귀 중위 순회
중위 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서로 방문합니다. 이진 검색 트리에서는 중위 순회가 항상 정렬된 수열을 생성합니다. 이 특성은 BST 검증, k번째로 작은 원소, BST를 정렬된 배열로 변환하는 문제 등에 사용됩니다. BST 문제에서 알아야 할 가장 중요한 순회입니다.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!재귀 후위 순회
후위 순회에서는 현재 노드보다 먼저 두 자식 노드를 모두 처리합니다. 부모의 계산이 자식들의 결과에 의존할 때 자연스러운 상향식 순서이며, 예를 들어 서브트리 크기 계산, 트리 삭제, 표현식 트리 평가에 사용됩니다. 정보를 위로 전달하는 대부분의 트리 문제는 암묵적인 후위 순회 논리를 사용합니다.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]스택을 사용한 반복 전위 순회
재귀 깊이 제한을 피하려면 명시적 스택을 사용해 DFS를 반복 방식으로 구현합니다. 전위 순회에서는 루트를 넣은 다음, 각 반복에서 노드를 꺼내 기록하고 오른쪽 자식과 왼쪽 자식을 차례로 넣습니다(왼쪽을 먼저 처리해야 하므로 오른쪽을 먼저 넣습니다). 이는 호출 스택의 LIFO 동작을 모방하며, Python의 기본 재귀 한도인 1000을 넘는 깊은 트리에서 가장 일반적으로 사용하는 방법입니다.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]스택을 사용한 반복 중위 순회
반복 중위 순회는 조금 더 까다롭습니다. 스택과 포인터 curr를 사용해 왼쪽으로 갈 수 있는 데까지 이동하면서 모든 노드를 넣습니다. 더 이상 왼쪽으로 갈 수 없으면 꺼내서 기록한 다음 오른쪽으로 이동합니다. 널이 될 때까지 왼쪽으로 넣고, 꺼내 처리한 다음 오른쪽으로 이동하는 이 패턴은 BST 반복자 문제에 등장하는 대표적인 반복 기법입니다.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]두 개의 스택을 사용하는 반복 후위 순회
반복 후위 순회에는 간단한 요령이 있습니다. 수정된 전위 순회(루트 → 오른쪽 → 왼쪽)를 수행한 뒤 결과를 역순으로 수집합니다. 루트를 넣고, pop한 노드를 결과의 앞에 추가한 다음 왼쪽과 오른쪽을 차례로 넣습니다. 순서를 뒤집으면 루트-오른쪽-왼쪽이 왼쪽-오른쪽-루트로 바뀌며, 이것이 바로 후위 순회입니다. 또는 prev 포인터를 사용해 하나의 스택으로 마지막 방문 노드를 추적할 수도 있습니다.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]순회를 선택하는 기준
올바른 순회를 선택하는 것은 면접에서 중요한 판단 기준입니다. 부모를 자식보다 먼저 처리해야 할 때는 전위 순회를 사용합니다(트리 직렬화, 구조 복사). BST에서는 정렬된 순서를 활용할 수 있으므로 중위 순회를 사용합니다. 두 자식 모두에 의존하는 값을 계산할 때는 후위 순회를 사용합니다(height, 지름, 서브트리 합). 최단 경로와 레벨별 그룹화 문제에는 BFS가 적합합니다.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6모리스 순회: O(1) 공간 중위 순회
모리스 순회는 트리를 임시로 수정하여 O(1) 공간에서 중위 순회를 수행합니다. 왼쪽 서브트리가 있는 각 노드에 대해 중위 선행자(왼쪽 서브트리에서 가장 오른쪽에 있는 노드)를 찾아 그 오른쪽 포인터를 현재 노드로 연결합니다. 방문한 후에는 연결을 복원합니다. 면접관이 ‘O(1)의 추가 공간으로 해결할 수 있나요?’라고 물을 때 상위권 면접에서 출제되는 고급 기법입니다.
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]순회 결과로 트리 재구성
전위 및 중위 배열이 주어지면 원래 트리를 재구성할 수 있습니다. 전위 배열의 첫 번째 원소는 항상 루트입니다. 중위 배열에서 해당 루트를 찾으면 왼쪽의 모든 원소는 왼쪽 서브트리에, 오른쪽의 모든 원소는 오른쪽 서브트리에 속합니다. 이 과정을 각 하위 배열에 재귀적으로 적용합니다. 해시 맵으로 인덱스를 조회하면 시간 복잡도는 O(n)입니다.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20순회의 시간 및 공간 복잡도 요약
세 가지 DFS 순회는 모든 노드를 정확히 한 번 방문하므로 시간 복잡도 O(n)을 가집니다. 공간 복잡도는 트리 height가 h일 때 O(h)이며, 균형 잡힌 트리에서는 O(log n), 한쪽으로 치우친 트리에서는 O(n)입니다(호출 스택 또는 명시적 스택 때문입니다). 반복 구현은 Python의 재귀 제한을 피하지만 점근적 공간 복잡도는 같습니다. 모리스 순회는 트리의 오른쪽 포인터를 재사용하여 유일하게 O(1) 공간을 달성합니다.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')빠른 확인
이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 확인해 보세요.
레슨 요약
이 레슨에서는 세 가지 DFS 순회 순서(전위, 중위, 후위)와 각각을 선택하는 기준, 명시적 스택을 사용하는 재귀 및 반복 구현, 그리고 모리스 O(1) 공간 기법을 배웠습니다. 다음 레슨에서는 이진 트리의 지름, height, 균형을 계산하는 방법을 살펴봅니다.
자주 묻는 질문
“중위, 전위, 후위 DFS” 강의는 무료인가요?
네 — “중위, 전위, 후위 DFS” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“중위, 전위, 후위 DFS”에서 뭘 배우나요?
세 가지 DFS 순회를 모두 명시적 스택을 사용한 재귀 및 반복 방식으로 구현하고, 각 순서가 유용한 경우를 설명합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“중위, 전위, 후위 DFS” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TreeNode 클래스와 레벨 순서 BFS
- 중위, 전위, 후위 DFS
- 지름, 높이, 균형 이진 트리
- 경로 합과 최소 공통 조상