30초 답변

Preorder는 root를 먼저 보고, inorder는 왼쪽-root-오른쪽 순서이며, postorder는 자식을 먼저 본 뒤 root를 봅니다. Level-order는 Queue를 사용해 위 레벨부터 차례로 방문합니다. 용도에 따라 순회 방식이 달라집니다.

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

1

2

3

4

5

DFS와 BFS는 tree traversal에서 어떻게 대응되나요?

Preorder, inorder, postorder는 깊이 방향으로 들어가는 DFS 계열이고, level-order는 같은 깊이를 먼저 보는 BFS 계열입니다.

이전 질문다음 꼬리질문

부가 설명

트리는 배열처럼 왼쪽에서 오른쪽으로 한 줄로만 읽히지 않습니다. 그래서 “부모를 먼저 볼지, 자식을 먼저 볼지, 같은 깊이를 먼저 볼지”를 정해야 합니다. 이 선택이 preorder, inorder, postorder, level-order의 차이입니다.

예를 들어 디렉터리 구조를 출력할 때는 부모를 먼저 보여주는 preorder가 자연스럽고, 폴더 용량을 계산할 때는 자식 용량을 먼저 알아야 하므로 postorder가 맞습니다. Binary Search Tree에서는 inorder로 순회하면 정렬된 순서로 값을 얻을 수 있습니다. 순회 방식은 이름보다 사용 목적과 연결해 기억하는 편이 좋습니다.

한 줄 정리

트리 순회는 노드를 방문하는 순서를 정해 문제에 맞는 계산 순서를 만드는 일입니다.