DFS와 BFS, 그리고 Preorder / Inorder / Postorder의 진짜 관계

트리나 그래프를 공부하다 보면 항상 함께 등장하는 개념이 있다.

• DFS / BFS

• Preorder / Inorder / Postorder

이 둘은 자주 묶여 설명되지만, 실제로는 역할과 레벨이 다르다.
이번 글에서는 다음 질문들에 답하는 흐름으로 정리해본다.

• DFS는 왜 순회 방식이 3가지로 나뉘는가?

• 순회 코드는 같은데 visit 위치만 다른 건가?

• BFS에는 왜 preorder / postorder 같은 개념이 없는가?

• 실무에서는 DFS보다 BFS를 언제 더 많이 쓰는가?

---

1. DFS와 BFS는 “탐색 전략”이다

먼저 가장 큰 개념부터 분리해야 한다.

DFS (Depth-First Search)

• 깊이를 우선으로 탐색

• 한 경로를 끝까지 내려간 후 되돌아옴

• 재귀 또는 스택 기반

BFS (Breadth-First Search)

• 너비(레벨)를 우선으로 탐색

• 같은 깊이의 노드를 먼저 모두 방문

• 큐 기반

DFS / BFS는 “어떻게 이동하느냐”에 대한 전략이다.

---

2. Preorder / Inorder / Postorder는 DFS의 변형이 아니다

많은 사람들이 이렇게 오해한다.

“DFS에는 preorder, inorder, postorder가 있다”

정확히 말하면 틀린 표현이다.

Preorder / Inorder / Postorder는
DFS를 ‘어떻게 관측하느냐’에 대한 규칙이다.

---

3. DFS는 구조적으로 3개의 “의미 있는 순간”을 가진다

재귀 DFS를 생각해보면, 모든 노드는 반드시 다음 세 시점을 거친다.

dfs(node)
 ├─ (1) node에 진입
 ├─ dfs(left)
 ├─ (2) 왼쪽 처리 완료
 ├─ dfs(right)
 └─ (3) node에서 나감

이 세 시점은 재귀 구조상 필연적이다.

👉 DFS가 3가지 순회로 나뉘는 이유는
노드를 처리할 수 있는 논리적 시점이 3곳뿐이기 때문이다.

---

4. “순회 코드는 같은데 visit 위치만 다른가?”

결론부터 말하면 정확히 맞다.

DFS의 이동 구조는 항상 동일하다.

function dfs(node) {
  if (!node) return;

  // A
  dfs(node.left);
  // B
  dfs(node.right);
  // C
}

node.val을 어디에서 사용하느냐에 따라 결과만 달라진다.

// Preorder
visit(node); // A

// Inorder
visit(node); // B

// Postorder
visit(node); // C

즉,

DFS는 하나이고,
pre/in/post는 관측 시점의 차이다.

---

5. 하나의 DFS로 3가지 순회를 동시에 얻을 수 있다

이 사실이 위 설명을 가장 명확히 증명한다.

function dfs(node) {
  if (!node) return;

  pre.push(node.val);     // enter
  dfs(node.left);
  in.push(node.val);      // between
  dfs(node.right);
  post.push(node.val);    // exit
}

• DFS는 단 한 번 실행

• 결과는 preorder / inorder / postorder 세 가지

👉 서로 다른 알고리즘이 아니다.

---

6. BFS에는 왜 visit 위치를 바꿀 수 없을까?

이제 BFS를 보자.

while (queue.length > 0) {
  const node = queue.shift();
  visit(node);
  queue.push(node.children);
}

BFS의 핵심 특징은 이것이다.

• 노드는 큐에서 꺼내지는 순간만 의미가 있다

• 재귀 호출 ❌

• enter / exit ❌

• 머무는 시간 ❌

DFS와 달리 BFS에는:

• “들어올 때”

• “중간”

• “나갈 때”

라는 개념이 존재하지 않는다.

👉 그래서 BFS에는 preorder / postorder가 생길 수 없다.

---

7. BFS는 왜 Level Order 하나뿐인가?

BFS의 정의 자체가 이것이기 때문이다.

“현재 레벨의 모든 노드를 처리한 후 다음 레벨로 이동한다”

이 성질은:

• visit을 dequeue 시점에 할 때만 유지된다

• 위치를 바꾸면 BFS의 의미가 깨진다

그래서 BFS 결과는 항상:

• Level Order Traversal

---

8. TypeScript로 보는 BFS 표준 구현

트리 BFS

function bfs(root: TreeNode | null): number[] {
  if (!root) return [];

  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

레벨 단위 BFS

function bfsByLevel(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const size = queue.length;
    const level: number[] = [];

    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      level.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

---

9. 실무에서는 왜 DFS보다 BFS를 더 많이 쓰는가?

1️⃣ 최단 거리 / 최소 단계

• 권한 관계

• 조직도

• 추천 시스템 n-hop

👉 “최소”가 들어가면 BFS

---

2️⃣ 단계적 확산 로직

• 알림 전파

• 피드 전파

• 영향도 계산

👉 BFS는 wave처럼 퍼진다

---

3️⃣ UI / UX 중심 데이터

• 댓글 트리

• 파일 탐색기

• 트리 UI

👉 사용자 인지는 깊이보다 레벨

---

4️⃣ 안정성

• DFS: stack overflow 위험

• BFS: 반복문 + 큐 → 안전

---

10. 그럼 DFS는 언제 쓰나?

DFS는 다음 상황에서 강력하다.

• 모든 경우의 수 탐색

• 백트래킹

• 구조 분석

• 사이클 탐지

• enter / exit 시간이 필요한 알고리즘

👉 DFS는 “구조”,
👉 BFS는 “거리와 단계”

---

11. 핵심 요약

• DFS / BFS는 탐색 전략이다

• Pre/In/Post는 DFS의 관측 규칙이다

• DFS는 구조적으로 3개의 방문 시점을 가진다

• BFS는 visit 위치를 바꿀 수 없다

• 실무에서는 “단계·최소·안정성” 때문에 BFS가 더 자주 쓰인다

---

마무리

DFS와 BFS는 단순한 알고리즘 문제가 아니라
데이터를 어떻게 이해하고 처리할 것인가에 대한 관점의 차이다.

이 차이를 정확히 이해하면:

• 알고리즘 문제 풀이

• 실무 설계

• 코드 리뷰

모두에서 판단이 훨씬 명확해진다.

---

🧾 작성 참고

이 글은 ChatGPT의 도움을 받아 내용을 정리하였습니다.