[Hackerrank 문제 풀이] Level Order Traversal

Junu Kim·2025년 12월 5일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

50/89

[Tree] Level Order Traversal

난이도: ★☆☆☆☆ • solved on: 2025-12-05

문제 요약

문제 유형: 트리, BFS
요구사항: 루트 노드부터 시작하여 레벨 순서(level-order)로 노드 값을 출력해야 한다.

사용 개념

자료구조
- Queue<Node> : BFS를 위한 핵심 자료구조
- ArrayDeque : Java에서 Queue 성능이 좋은 구현체
알고리즘/기법
- BFS (Breath First Search, 너비 우선 탐색)
- Queue 기반 순차 순회
핵심 키워드
- level-order traversal
- breadth-first search
- queue poll/add

풀이 아이디어

문제 분해

레벨 순서는 BFS 수행 순서와 동일하다.

루트 노드를 큐에 넣는다.

큐가 빌 때까지 다음을 반복한다:

노드를 꺼낸다.

왼쪽 자식이 있으면 큐에 넣는다.

오른쪽 자식이 있으면 큐에 넣는다.

현재 노드의 값을 출력한다.
핵심 로직 흐름
queue.add(root)
while queue not empty:
    node = queue.poll()
    print(node.data)
    if node.left exists → queue.add(left)
    if node.right exists → queue.add(right)
예외 처리

root가 null인 경우 → 출력 없이 종료

코드

public static void levelOrder(Node root) {
    if (root == null) return;

    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node tmpNode = queue.poll();

        if (tmpNode.left != null) {
            queue.add(tmpNode.left);
        }

        if (tmpNode.right != null) {
            queue.add(tmpNode.right);
        }

        System.out.print(tmpNode.data + " ");
    }
}

시간·공간 복잡도

시간 복잡도: O(N) — 모든 노드를 한 번씩 방문
공간 복잡도: O(N) — 최악의 경우 큐에 트리 한 레벨이 모두 담기는 경우

어려웠던 점

preorder, inorder, postorder를 모두 재귀로 해결한 경험 때문에 본 문제도 재귀적으로 풀 수 있을 것이라 고정관념이 생겼다.
level-order는 DFS 성격의 재귀와 달리 BFS 기반이라 queue 중심 접근이 필요했음을 떠올리는 데 시간이 걸렸다.
BFS는 항상 큐라는 점을 다시 확인할 수 있었다.