"트리를 걷는다는 건 일을 언제 할지 정하는 거야. 자식보다 먼저 할지, 자식들 사이에 할지, 자식 다음에 할지, 아니면 아예 한 레벨씩 통째로 훑을지. 타이밍이 달라지면 순회가 달라지고, 각각 맞는 일이 따로 있어."
세 가지 깊이 우선 순서
이진 트리에서 깊이 우선 순회 셋은 딱 하나만 달라. 자식으로 재귀해 들어가는 시점을 기준으로 노드를 언제 방문하느냐야.
- 전위(pre-order)는 노드 → 왼쪽 → 오른쪽 순서야. 자식보다 먼저 노드를 방문하지. 트리를 복사하거나 직렬화할 때, 구조를 위에서 아래로 출력할 때 써. 부모를 후손보다 먼저 처리하는 거니까.
- 중위(in-order)는 왼쪽 → 노드 → 오른쪽이야. 두 서브트리 사이에 노드를 방문해. 이진 탐색 트리에서는 키가 정렬된 순서로 나와. 이 트랙에서 가장 쓸모 있는 순회 사실이야.
- 후위(post-order)는 왼쪽 → 오른쪽 → 노드고, 자식을 다 본 뒤에 노드를 방문해. 노드의 결과가 자식의 결과에 달려 있을 때 쓰지. 크기나 높이를 아래에서 위로 계산하거나, 트리를 해제하고 삭제하거나(자식 먼저), 수식 트리를 계산할 때야.
셋 다 재귀 세 줄이면 끝나고, 움직이는 건 재귀 호출 두 개를 기준으로 "이 노드를 방문한다"는 줄을 어디에 놓느냐뿐이야.
네 번째: 레벨 순회 (BFS)
레벨 순회는 노드를 깊이 순서로 방문해. 루트를 보고, 깊이 1을 전부 보고, 깊이 2를 전부 보는 식으로 트리를 수평으로 훑지. 그리고 이건 재귀가 아니야. 큐를 써. 스택과 큐 트랙에서 본 너비 우선 기계장치 그대로야. 노드를 꺼내고, 방문하고, 자식을 넣고, 반복. 트리를 레벨별로 출력하거나 어떤 조건에 맞는 가장 얕은 노드, 그러니까 루트에서 가장 적은 단계에 닿는 노드를 찾을 때 써. 깊이 우선 순서는 스택을 쓰고(또는 콜 스택을 쓰고) 레벨 순회는 큐를 써. 앞에서 배운 그 짝 관계를 트리에 그대로 적용한 거야.
전위, 중위, 후위는 노드를 언제 방문하느냐만 달라. 자식보다 먼저냐, 사이냐, 다음이냐. 셋 다 재귀고 셋 다 스택 기반이야. 레벨 순회는 큐로 깊이별로 방문하는 BFS고. BST의 중위 순회는 정렬된 키를 내놓고, 후위 순회는 아래에서 위로 올라오는 일에 맞아.
맞는 걷기 고르기
순회는 아무거나 고르는 게 아니라 필요에 따라 정해져. 값을 정렬된 순서로 원하면 BST에 중위. 자식보다 부모를 먼저 처리해야 하면(직렬화, 복사) 전위. 부모보다 자식의 답이 먼저 필요하면(크기, 삭제, 수식 계산) 후위. 루트에 가장 가까운 걸 찾거나 레벨별로 보고 싶으면 큐를 쓰는 레벨 순회. 트리 문제에서 막혔을 때 "이건 어떤 순회를 원하는 문제지?"만 물어도 답의 대부분이 나올 때가 많아.
피파의 고백
나는 전위, 중위, 후위를 각각 다른 알고리즘으로 외웠고 늘 헷갈렸어. 아빠가 질문 하나로 정리해 버렸지. "노드를 언제 건드려 — 애들 전, 사이, 후?" 재귀 골격은 하나고 움직이는 건 줄 하나뿐이었던 거야. 그리고 BST에서 왼쪽-노드-오른쪽 순으로 읽기만 했는데 정렬된 결과가 공짜로 떨어진다는 걸 깨달은 날, 트리가 기계적인 암기 대상에서 누군가 일부러 설계한 물건으로 느껴지기 시작했어.