[Hackerrank 문제 풀이] Preorder Traversal

Junu Kim·2025년 12월 5일

Java hackerrank

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

목록 보기

47/89

[Tree] Preorder Traversal

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

문제 요약

문제 유형: 트리 순회(Preorder Traversal), 재귀
요구사항: 주어진 트리의 root부터 전위 순회(preorder traversal) 방식으로 노드 값을 한 줄에 공백으로 구분하여 출력해야 한다.

사용 개념

자료구조
- 이진트리(Node 구조)
알고리즘/기법
- 재귀(recursion)
- 전위 순회(pre-order traversal)

핵심 키워드

root → left → right 출력 순서 (Preorder)

참고

In-order Traversal : left → root → right

Post-order Traversal : left → right → root

Traversal 출력 순서 루트 출력 시점 주요 특징
Pre-order root → left → right 맨 처음 트리 복원, 구조 출력
In-order left → root → right 중간 BST 정렬 결과 출력
Post-order left → right → root 맨 마지막 서브트리 작업 후 root 처리

Traversal	출력 순서	루트 출력 시점	주요 특징
Pre-order	root → left → right	맨 처음	트리 복원, 구조 출력
In-order	left → root → right	중간	BST 정렬 결과 출력
Post-order	left → right → root	맨 마지막	서브트리 작업 후 root 처리

풀이 아이디어

문제 분해

Preorder 규칙: (1) root 출력 → (2) 왼쪽 재귀 → (3) 오른쪽 재귀

null 이면 더 내려갈 곳이 없으므로 return 한다.
핵심 로직 흐름
preOrder(root):
    if root is null: return (base case)
    print root.data + " "
    preOrder(root.left)
    preOrder(root.right)
예외 처리

root가 null일 수 있는 테스트가 존재하므로 null 체크 필요

반드시 print(ln 아님)로 출력해야 HackerRank의 기대 출력 형식과 일치함

코드

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

    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

시간·공간 복잡도

시간 복잡도: O(N)
(모든 노드를 정확히 한 번씩 방문)
공간 복잡도: O(H)
(재귀 호출 스택 깊이 = 트리 높이)

어려웠던 점

처음에는 System.out.println()을 사용해 출력이 줄바꿈 형태로 나와 문제 형식과 맞지 않았다.
출력 포맷이 까다로운 HackerRank 특성상 공백·줄바꿈 차이 때문에 채점 실패가 발생함.

배운 점 및 팁

트리 순회 문제는 대부분 출력 형식 때문에 오답이 나올 수 있으므로 print vs println 여부를 반드시 확인해야 한다.
Preorder는 항상 "root 먼저" 출력한다는 규칙만 기억하면 된다.
HackerRank의 트리 문제는 대부분 재귀를 기본 전제로 한다.
- 트리는 순회를 통해 전체 node를 탐색하는게 목적이기 때문에 Iteration, Memoization, Tail Recursion과 같은 최적화가 불가능하다.