Traversal trace

같은 트리도 기록 시점이 순서를 바꾼다

전위, 중위, 후위는 모두 DFS이지만 현재 노드를 언제 기록하는지가 다릅니다. BFS는 큐에서 꺼내는 레벨 순서가 기준입니다.

예시 트리

A B C D E F

A의 왼쪽은 B, 오른쪽은 C이며 B는 D와 E, C는 F를 가집니다.

pre A B D E C F 기록 후 내려감
in D B E A C F 왼쪽 뒤 기록
post D E B F C A 자식 뒤 기록
bfs A B C D E F 큐에서 꺼냄
방문 시점

출력 누락은 대부분 현재 노드를 기록하는 위치가 한 줄 어긋났을 때 발생합니다.

상태 공간

DFS는 높이 H, BFS는 최대 폭 W를 기준으로 보조 공간을 봅니다.

반례 입력

완전 트리만 통과해도 편향 트리와 빈 트리에서 실패할 수 있습니다.