[Tree] Inorder Traversal

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

---

문제 요약

• 문제 유형: 트리 순회(In-order Traversal)
• 요구사항: 주어진 이진트리에 대해 중위 순회(left → root → right) 진행 후, 노드 값을 공백으로 구분하여 한 줄에 출력한다.

---

사용 개념

1. 자료구조

   • Binary Tree (Node 구조)

2. 알고리즘/기법

   • 재귀(recursive traversal)
   • In-order traversal

3. 핵심 키워드

   • left → root → right
   • 재귀 호출 구조

---

풀이 아이디어

1. 문제 분해

• root가 null이면 더 이상 방문할 노드가 없으므로 즉시 return 한다.
• In-order 순서:
  (1) 왼쪽 노드 방문 → (2) 현재 루트 출력 → (3) 오른쪽 노드 방문

2. 핵심 로직 흐름

   inOrder(root):
       if root is null → return
       inOrder(root.left)
       print root.data + " "
       inOrder(root.right)

3. 예외 처리

   • null 노드 체크는 필수

---

코드

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

    if (root.left != null) {
        inOrder(root.left);
    }

    System.out.print(root.data + " ");

    if (root.right != null) {
        inOrder(root.right);
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(N)
  전체 노드를 정확히 한 번 방문
• 공간 복잡도: O(H)
  H = 트리 높이 (재귀 스택 사용)

---

어려웠던 점

• 재귀 순서(left → root → right)가 자연스럽지 않아 혼동될 수 있음.

---

배운 점 및 팁

• In-order traversal은 BST에서 오름차순 정렬된 값을 얻을 때 사용되는 핵심 개념이다.
• 순회 문제는 재귀가 가장 직관적이며 시간적 개선 여지는 없다. (O(N) 최소)

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/contests/2021-fall/challenges/tree-inorder-traversal/problem

• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 트리 순회 - Baekjoon 1991
  • Binary Tree Inorder Traversal - Baekjoon 22856
  • Tree: Preorder Traversal - HackerRank

• 확장 문제 (GPT 추천)

  • Tree: Postorder Traversal - HackerRank
  • Binary Search Tree : Insertion - HackerRank