[Tree] Postorder Traversal

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

---

문제 요약

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

---

사용 개념

1. 자료구조

   • Binary Tree(Node)

2. 알고리즘/기법

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

3. 핵심 키워드

   • left → right → root 출력 규칙
   • 재귀 호출 순서에 따른 출력 구조

---

풀이 아이디어

1. 문제 분해

• Post-order 규칙:
  (1) 왼쪽 서브트리 방문 → (2) 오른쪽 서브트리 방문 → (3) 루트 출력

• root가 null이면 더 진행할 필요 없으므로 return.

2. 핵심 로직 흐름

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

3. 예외 처리

   • 재귀 호출 순서를 left → right → root 로 지켜야 함

---

코드

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

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

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

---

시간·공간 복잡도

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

---

어려웠던 점

• 알고리즘 순서는 알고 있었지만, 처음 구현 시 right → root → left 형태로 잘못된 순서를 작성해 rightmost 노드부터 출력되는 오답이 발생하였다. (그래서 계획해서 맞추기다기 보다는 여러 방면으로 해보다가 때려 맞춘 것에 가까웠다.)

---

배운 점 및 팁

• Post-order는 루트 출력이 가장 마지막이므로, 항상 left → right → root 를 머릿속에 명확히 그려두는 것이 중요하다.
• Tree 문제는 대부분 시간 복잡도 개선 여지가 없으며, 재귀 구조가 가장 읽기 쉽고 직관적이다.
• Debugging 시 작은 트리를 그려놓고 직접 순서를 따라가면 빠르게 오류를 찾을 수 있다.

---

참고 및 링크

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

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

---

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 트리 순회 - Baekjoon 1991
  • Binary Tree Postorder Traversal - LeetCode
  • Tree: Preorder Traversal - HackerRank

• 확장 문제 (GPT 추천)

  • Tree: Level Order Traversal - HackerRank
  • Binary Search Tree : Lowest Common Ancestor - HackerRank