트리의 순회

트리 순회(Traversal)

배열이나 리스트처럼 선형 구조는 처음부터 끝까지 차례대로 방문하면 된다.
하지만 트리(Tree) 는 계층 구조이므로 노드를 어떤 순서로 방문할지에 따라 다양한 방법이 존재한다.

방문(Visit)과 순회(Traversal)

• 방문(Visit) : 특정 노드에 도달했을 때 수행하는 동작(출력·계산·저장 등)
• 순회(Traversal) : 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 전체 과정

즉, 순회는 “방문 순서를 정한 동선” 이고, 방문은 “노드에 도달했을 때 하는 작업” 이다.

깊이 우선 순회(DFS)

DFS(Depth-First Search)는 한 갈래를 끝까지 따라간 뒤 돌아오는 방식이다.
노드를 언제 방문(출력)하느냐에 따라 다음 3가지 순회가 있다.

1. 전위 순회(Preorder)

• 순서: 부모 → 왼쪽 자식 → 오른쪽 자식
• 특징: 부모를 먼저 처리하고 자식으로 내려감

void preorder(Node root) {
    if (root == null) return;
    System.out.println(root.value); // 부모 먼저
    preorder(root.left);
    preorder(root.right);
}

예시 방문 순서: A → B → C → D …

2. 중위 순회(Inorder)

• 순서: 왼쪽 자식 → 부모 → 오른쪽 자식
• 특징: 이진 트리(Binary Tree) 에서만 의미가 있음

void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.value); // 부모는 가운데
    inorder(root.right);
}

예시 방문 순서: C → B → D → A → …

3. 후위 순회(Postorder)

• 순서: 왼쪽 자식 → 오른쪽 자식 → 부모
• 특징: 자식 노드를 모두 처리한 후 부모를 처리

void postorder(Node root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.value); // 부모 마지막
}

예시 방문 순서: C → D → B → A …

시간 복잡도

세 방식 모두 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)

레벨 순서 순회(Level-Order, BFS)

DFS가 깊게 내려가는 방식이라면, BFS(Breadth-First Search) 는 같은 깊이(레벨)에 있는 노드들을 먼저 방문하는 방식

        A
      / | \
     B  C  D
    / \    / \
   E  F   G   H
          /
         I

방문 순서: A → B, C, D → E, F, G, H → I

BFS 코드 구현 (큐 사용)

List<Integer> bfs(Node root) {
    if (root == null) return Collections.emptyList();

    List<Integer> result = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.remove();
        result.add(node.value);

        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return result;
}

시간 복잡도

모든 노드를 정확히 한 번씩 큐에서 꺼내므로 BFS 역시 O(n)