트리 기초

🎯 학습 목표

이 강을 마치면 트리의 기본 용어(루트·리프·부모·자식·깊이·높이)를 정확히 쓰고, 이진 트리를 노드 클래스로 구현할 수 있습니다. 그리고 전위·중위·후위·레벨 순회 네 가지를 재귀와 반복 양쪽으로 다룰 수 있게 됩니다.

트리는 계층 구조를 표현하는 자료구조입니다. 파일 시스템, 조직도, 문서 구조가 전부 트리입니다. 그리고 20강 이진 탐색 트리, 21강 힙, 23강 DFS가 모두 이 강 위에 올라갑니다.

💡 트리 용어 정리

트리는 사이클이 없고 하나의 루트에서 뻗어 나가는 구조입니다. 18강의 연결 리스트가 다음 노드를 하나만 가졌다면, 트리는 여러 개의 자식을 가집니다.

트리 구조와 용어

                    1          ← 루트(root) : 부모가 없는 노드
                  /   \
                 2     3       ← 1의 자식(child), 서로 형제(sibling)
                / \     \
               4   5     6     ← 4,5,6 은 리프(leaf) : 자식이 없음
              /
             7

  깊이(depth)  루트에서 그 노드까지의 간선 수
               1은 0, 2·3은 1, 4·5·6은 2, 7은 3

  높이(height) 그 노드에서 가장 먼 리프까지의 간선 수
               트리 전체의 높이 = 루트의 높이 = 3

  레벨(level)  같은 깊이의 노드 묶음
               레벨 0: [1]  레벨 1: [2,3]  레벨 2: [4,5,6]

  서브트리     어떤 노드와 그 아래 전체
               2의 서브트리 = {2, 4, 5, 7}

  ▲ 트리의 성질
   · 노드가 n개면 간선은 반드시 n-1개
   · 임의의 두 노드를 잇는 경로는 유일하다
   · 사이클이 없다

  이진 트리 — 자식이 최대 2개

                 1
               /   \
              2     3
             / \
            4   5

   포화 이진 트리 : 모든 레벨이 꽉 참
   완전 이진 트리 : 마지막 레벨만 왼쪽부터 채워짐 (21강 힙)
   편향 트리      : 한쪽으로만 뻗음 → 사실상 연결 리스트

  ▲ 높이가 왜 중요한가
    균형 잡힌 이진 트리의 높이는 약 log n 이다.
    → 루트에서 리프까지 O(log n)
    편향되면 높이가 n이 된다 → O(n)  ★
    20강 이진 탐색 트리의 성능이 여기에 달려 있다.

📖 네 가지 순회

순회(traversal)는 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 것입니다. 언제 자기 자신을 처리하느냐에 따라 세 가지로 나뉩니다.

순회 순서 비교 (아래 트리 기준)

                 1
               /   \
              2     3
             / \
            4   5

  전위(preorder)   자기 → 왼쪽 → 오른쪽
                   1, 2, 4, 5, 3
                   ▲ 트리를 '복사'하거나 구조를 출력할 때

  중위(inorder)    왼쪽 → 자기 → 오른쪽
                   4, 2, 5, 1, 3
                   ▲ 이진 탐색 트리에서 '정렬된 순서'가 나온다 (20강)

  후위(postorder)  왼쪽 → 오른쪽 → 자기
                   4, 5, 2, 3, 1
                   ▲ 자식을 다 처리한 뒤 부모를 처리
                     (폴더 용량 계산, 트리 삭제 등)

  레벨(BFS)        위에서 아래로, 왼쪽에서 오른쪽으로
                   1, 2, 3, 4, 5
                   ▲ 큐를 쓴다 (6강) — 재귀가 아니다  ★

  ▲ 앞의 세 개는 모두 DFS 계열이다
    깊이 먼저 내려갔다가 되돌아온다 → 재귀·스택

  ▲ 레벨 순회만 BFS 계열이다
    가까운 것부터 훑는다 → 큐

  복잡도
   네 가지 모두 각 노드를 한 번씩 방문 → 시간 O(n)
   공간: DFS 는 O(높이), BFS 는 O(레벨의 최대 너비)

세 가지 DFS 순회의 차이는 "자기 자신을 처리하는 코드 줄이 어디 있는가" 하나뿐입니다. 재귀 호출 앞·사이·뒤 중 어디에 두느냐로 결정됩니다.

💻 실전 예제 — 순회와 트리 계산

from collections import deque


class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def preorder(node, result):
    """자기 → 왼쪽 → 오른쪽"""
    if not node:
        return
    result.append(node.value)      # 여기서 처리
    preorder(node.left, result)
    preorder(node.right, result)


def inorder(node, result):
    """왼쪽 → 자기 → 오른쪽"""
    if not node:
        return
    inorder(node.left, result)
    result.append(node.value)      # 위치만 바뀐다
    inorder(node.right, result)


def level_order(root):
    """레벨 순회 → 큐 사용, 레벨별로 묶어서 반환"""
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        size = len(q)              # 이번 레벨의 노드 수  ★
        level = []
        for _ in range(size):
            node = q.popleft()
            level.append(node.value)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result


def height(node):
    """트리 높이 (간선 기준) → 후위 순회 방식"""
    if not node:
        return -1                  # 빈 트리는 -1, 리프는 0
    return 1 + max(height(node.left), height(node.right))


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

pre, ino = [], []
preorder(root, pre)
inorder(root, ino)
print(pre)                  # [1, 2, 4, 5, 3]
print(ino)                  # [4, 2, 5, 1, 3]
print(level_order(root))    # [[1], [2, 3], [4, 5]]
print(height(root))         # 2

코드를 줄 단위로 보겠습니다.

• if not node: return — 기저 조건입니다(13강). 빈 노드에 도달하면 그냥 돌아옵니다. 이 줄이 없으면 None.left에서 오류가 납니다.
• result.append(node.value)의 위치 — 전위와 중위 함수는 이 한 줄의 위치만 다릅니다. 후위는 재귀 호출 두 개 뒤에 두면 됩니다.
• size = len(q) — 레벨 순회의 핵심입니다. 반복을 시작하기 전에 현재 큐의 크기를 고정해야 이번 레벨만 처리됩니다. 이 줄이 없으면 레벨 구분이 무너집니다.
• q.popleft() — 덱을 씁니다(6강). list.pop(0)을 쓰면 O(n)이라 전체가 O(n²)가 됩니다.
• if node.left: q.append(node.left) — 존재할 때만 큐에 넣습니다. None을 넣으면 다음 반복에서 오류가 납니다.
• return -1 — 간선 기준 높이의 관례입니다. 빈 트리를 -1로 두면 리프가 자연스럽게 0이 됩니다. 노드 기준으로 세는 정의도 있으므로 문제가 어느 기준인지 반드시 확인하세요.
• 1 + max(height(left), height(right)) — 후위 순회 구조입니다. 자식의 값을 모두 받은 뒤 자기 값을 계산합니다. 트리에서 값을 아래에서 위로 모으는 모든 문제가 이 형태입니다.

마지막 함수가 특히 중요합니다. "서브트리의 답을 받아 내 답을 만든다"는 패턴은 트리 문제의 가장 흔한 형태입니다. 노드 개수 세기, 합 구하기, 최댓값 찾기가 전부 같은 구조입니다.

⚠️ 자주 하는 실수

첫째, None 검사를 빠뜨립니다. 트리 문제 오류의 대부분이 여기서 납니다. 재귀 함수의 첫 줄을 if not node로 시작하는 습관을 들이세요.

둘째, 레벨 순회에서 size를 고정하지 않습니다. for _ in range(len(q))를 반복 중에 쓰면 큐가 늘어나면서 조건도 바뀝니다. 미리 변수에 담아야 합니다.

셋째, 높이와 깊이를 혼동합니다. 깊이는 위에서 아래로, 높이는 아래에서 위로 셉니다. 그리고 간선 기준인지 노드 기준인지에 따라 답이 1 차이 납니다. 문제 정의를 확인하세요.

넷째, 재귀 깊이를 고려하지 않습니다. 편향 트리는 높이가 n입니다. 노드가 10만 개인 편향 트리를 재귀로 순회하면 RecursionError가 납니다(13강). 스택을 쓴 반복 구현이나 한도 상향이 필요합니다.

다섯째, 레벨 순회를 재귀로 짜려 합니다. 레벨 순회는 큐가 본질입니다. 재귀는 깊이 우선이라 구조가 맞지 않습니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	노드 n개면 간선 n-1개, 사이클 없음
2	균형 트리 높이는 약 log n, 편향되면 n
3	전위·중위·후위는 자기 처리 위치만 다르다
4	레벨 순회는 큐 — DFS가 아니다
5	레벨 구분은 size 고정
6	재귀 첫 줄은 if not node
7	자식의 답을 받아 내 답을 — 트리 문제의 기본형

지금 해 볼 것은 후위 순회 함수를 직접 써 보는 것입니다. preorder를 복사해 append 줄을 맨 아래로 옮기기만 하면 됩니다. 결과가 [4, 5, 2, 3, 1]이 나오면 성공입니다.

다음 20강 「이진 탐색 트리」에서는 트리에 정렬 규칙을 넣습니다. 왼쪽은 작고 오른쪽은 큰 구조를 만들면 탐색·삽입·삭제를 평균 O(log n)에 할 수 있습니다. 그리고 중위 순회가 왜 정렬된 결과를 주는지도 이 강에서 밝혀집니다.

📚 참고 자료

• Classes — Python 공식 문서
• collections.deque — Python 공식 문서
• sys.setrecursionlimit() — Python 공식 문서