C-1: 트리와 이진트리 — "노드가 자식 둘을 가리키면, 데이터가 가지를 친다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 해시 테이블로 "값 자체로 위치를 계산해 평균 O(1)에 찾기"까지 왔습니다. 이걸로 카테고리 B, 선형 자료구조가 끝났어요. 스택·큐·연결 리스트·해시 — 모양은 달라도 전부 데이터를 한 줄로 늘어놓는 그릇이었습니다. 쌓거나, 줄 세우거나, 이어 붙이거나, 칸에 흩어 두거나.

오늘부터는 데이터가 한 줄이 아니라 가지를 치는 비선형 구조로 넘어갑니다. 첫 주자는 트리(tree)예요. 연결 리스트의 노드가 next 하나로 "다음 하나"만 가리켰다면, 트리의 노드는 왼쪽·오른쪽 두 포인터로 "자식 여럿"을 가리킵니다. 가계도처럼 위에서 아래로 갈라지는 구조죠. 지난 시간에 잡은 노드와 포인터 감각이 그대로 이어지니, 한 노드가 여러 노드를 가리키는 그림을 떠올리며 시작해 봅시다.

트리는 난이도가 한 칸 올라갑니다. 특히 트리를 훑는 순회를 재귀로 짜는 대목이 첫 고비예요. 하지만 원리는 단순합니다. "트리는 루트 하나에 작은 트리(서브트리)가 매달린 구조"라는 한 문장이면 순회도 탐색도 다 풀립니다.

 오늘의 여정 — "노드가 자식 둘을 가리키면, 데이터가 가지를 친다"

 [1] 트리 용어        →  루트·리프·부모/자식·높이·깊이 (가계도의 언어)
 [2] 이진트리 만들기   →  노드 하나에 왼쪽·오른쪽 두 포인터 (연결 리스트의 확장)
 [3] 전위 순회        →  나 → 왼 → 오, 재귀로 트리를 타고 내려간다
 [4] 중위·후위 순회    →  '나를 언제 방문하느냐'만 바꾼다 (중위 = 정렬)
 [5] 반복 순회        →  재귀의 숨은 스택을 손으로 꺼낸다
 [6] BST 삽입         →  왼쪽은 작게, 오른쪽은 크게
 [7] BST 탐색         →  절반씩 버려 평균 O(log n), 치우치면 최악 O(n)
 [8] 트리로 답 구하기   →  높이·노드 수·지름 (자식 결과를 모아 부모 답)

자, 데이터가 가지를 치는 첫 그릇을 만들러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "트리를 노드와 두 포인터로 직접 만들고, 세 가지 순회(전위·중위·후위)를 재귀와 반복으로 짜며, 이진탐색트리의 삽입·탐색이 평균 O(log n)인 까닭과 한쪽으로 치우치면 최악 O(n)으로 무너지는 이유를 손으로 확인한다"

🎯 학습 목표

• 트리 용어(루트·리프·높이·깊이)를 잡고, 노드의 왼쪽·오른쪽 두 포인터로 이진트리를 직접 만듭니다.
• 전위·중위·후위 순회를 재귀로 짜고, 재귀의 숨은 스택을 명시적 스택으로 바꿔 반복 순회까지 구현합니다(순회는 시간 O(n)·공간 O(h)).
• 이진탐색트리(BST)의 삽입·탐색이 평균 O(log n)·최악 O(n)인 이유를 트리 높이로 설명하고, 트리의 지름 같은 문제를 한 번의 순회로 O(n)에 풉니다.

Step 1: "가지를 치는 데이터" — 트리 용어

지금까지 배운 그릇은 전부 한 줄이었습니다. 배열은 원소가 옆으로 나란히, 연결 리스트는 노드가 앞뒤로 이어졌죠. 오늘의 트리는 다릅니다. 한 노드가 아래로 여러 갈래로 갈라져요. 가장 익숙한 예가 가계도입니다. 맨 위 조상 한 명에서 자식들로, 그 자식의 자식들로 아래로 뻗어 나가죠.

트리를 다루려면 먼저 그 언어를 익혀야 합니다. 용어가 곧 지도예요.

         (A)
         / \
       (B) (C)
       / \    \
     (D) (E)  (F)

  루트(root)    : 맨 위, 부모가 없는 노드 → A
  리프(leaf)    : 자식이 없는 노드 → D, E, F (잎)
  부모-자식      : A는 B·C의 부모(parent), B·C는 A의 자식(child)
  간선(edge)    : 부모와 자식을 잇는 선
  서브트리        : 어떤 노드와 그 아래 전부 (B와 D·E는 하나의 서브트리)

여기에 두 가지 수치가 더 붙습니다. 깊이(depth)는 루트에서 그 노드까지 내려온 간선의 수예요(루트의 깊이는 0). 높이(height)는 반대로, 그 노드에서 가장 먼 리프까지 내려가는 간선의 수입니다(리프의 높이는 0). 트리 전체의 높이는 루트의 높이고요. 위 그림에서 A→D는 간선 2개라 D의 깊이는 2, 트리의 높이도 2입니다.

오늘 다루는 건 그중에서도 이진트리(binary tree)입니다. 자식이 최대 둘(왼쪽·오른쪽)로 제한된 트리예요. 코딩테스트에 나오는 트리는 대부분 이 이진트리라, 여기에 집중합니다.

🎯 코테에서는 트리 문제가 "이 트리의 무엇을 구하나"로 시작합니다. 높이·노드 수·특정 경로·최댓값처럼요. 그리고 트리는 사실 사이클(고리) 없이 연결된 특수한 그래프인데, 이 관계는 그래프를 배울 때 다시 만납니다. 오늘은 "위에서 아래로 갈라지는 구조"로만 봐도 충분해요.

💡 한 줄 정리

트리는 한 노드가 아래로 여러 자식으로 갈라지는 비선형 구조다. 루트(맨 위)·리프(잎)·부모/자식·깊이(위에서 내려온 간선 수)·높이(아래로 내려갈 간선 수)가 트리를 읽는 기본 언어이고, 자식이 최대 둘인 이진트리를 주로 다룬다.

Step 2: "노드 하나에 두 포인터" — 이진트리를 코드로

이제 용어를 코드로 옮깁니다. 연결 리스트의 노드는 값 하나와 next 하나였죠. 트리의 노드는 값 하나에 왼쪽·오른쪽 두 포인터를 답니다. 딱 그 차이뿐이에요.

# structures/binary_tree.py
class TreeNode:
    """이진트리의 노드: 값 하나와 왼쪽·오른쪽 자식을 가리키는 포인터 둘.

    연결 리스트 노드가 next 하나였다면, 트리 노드는 left·right 둘이다.
    자식이 없으면 그 포인터는 None이다(리프 노드는 둘 다 None).
    """

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left        # 왼쪽 자식(없으면 None)
        self.right = right      # 오른쪽 자식(없으면 None)

노드가 있으면 트리는 노드를 이어 붙여 만듭니다. 아래 표본 트리를 손으로 조립해 볼게요. 리프부터 만들어 위로 붙여 올라갑니다.

def build_sample_tree():
    n4, n5, n6 = TreeNode(4), TreeNode(5), TreeNode(6)
    n2 = TreeNode(2, n4, n5)
    n3 = TreeNode(3, None, n6)
    return TreeNode(1, n2, n3)

이 코드가 만드는 트리는 이렇게 생겼습니다. 오늘 순회 예시에 계속 쓸 트리라 눈에 익혀 두세요.

        1
       / \
      2   3
     / \   \
    4   5   6

값 1이 루트고, 왼쪽 자식 2 아래에 4·5가, 오른쪽 자식 3 아래에 6이 매달렸습니다. 3은 왼쪽 자식이 없어 TreeNode(3, None, n6)처럼 왼쪽을 None으로 뒀어요. 노드 하나에 접근하는 건 O(1), 트리 전체를 만드는 건 노드 수만큼이라 O(n)입니다.

실전 코테에선 트리를 이렇게 클래스로 짜기도 하지만, 노드가 문제로 이미 주어지거나(LeetCode의 TreeNode), 부모-자식 관계를 딕셔너리로 표현하기도 합니다. 어느 쪽이든 "노드 하나가 자식들을 가리킨다"는 뼈대는 같아요.

🎯 코테에서는 LeetCode의 트리 문제가 바로 이 TreeNode 클래스(val·left·right)를 그대로 줍니다. 문제 설명에 클래스가 미리 정의돼 있고, 여러분은 그 노드를 받아 순회하거나 값을 구하면 돼요. 그래서 노드 구조를 미리 파악해 두는 게 트리 문제의 출발점입니다.

💡 한 줄 정리

이진트리의 노드는 값 하나와 왼쪽·오른쪽 두 포인터를 가진다. 자식이 없으면 그 포인터는 None(리프는 둘 다 None)이다. 노드를 이어 붙여 트리를 만들고, 노드 접근은 O(1)·트리 구성은 O(n)이다.

Step 3: "트리를 훑는 법 ① 전위 순회" — 재귀로 타고 내려간다

트리를 만들었으면 이제 훑어야(순회, traversal) 합니다. 순회란 모든 노드를 빠짐없이 한 번씩 방문하는 거예요. 그런데 트리는 한 줄이 아니라 갈래가 있어서, "어느 순서로 방문하느냐"를 정해야 합니다.

여기서 재귀(recursion)가 등장합니다. 재귀란 함수가 자기 자신을 부르는 기법이에요. 트리와 궁합이 완벽한데, 이유가 있습니다. 트리는 "루트 하나 + 왼쪽 서브트리 + 오른쪽 서브트리"인데, 그 서브트리도 또 하나의 트리거든요. 그러니 "트리를 순회한다"를 "루트를 방문하고, 왼쪽 서브트리를 순회하고, 오른쪽 서브트리를 순회한다"로 적으면, 자기 자신을 다시 부르는 재귀가 자연스럽게 나옵니다. 끝나는 조건은 하나예요. 빈 트리(None)에 닿으면 아무것도 안 하고 돌아옵니다.

가장 먼저 배울 순회는 전위 순회(preorder)입니다. "나 → 왼쪽 → 오른쪽" 순서로, 루트를 가장 먼저 찍어요.

# structures/binary_tree.py
def preorder(node):
    """전위 순회: 나 → 왼쪽 → 오른쪽. 방문값을 리스트로 모아 돌려준다.

    루트를 가장 먼저 찍고 왼쪽 서브트리, 그다음 오른쪽 서브트리로 내려간다.
    표본 트리면 [1, 2, 4, 5, 3, 6]. 시간 O(n), 공간 O(h)(재귀 깊이).
    """
    if node is None:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

딱 두 줄입니다. "빈 트리면 빈 리스트", 아니면 "내 값 + 왼쪽 순회 결과 + 오른쪽 순회 결과". 이 함수가 표본 트리를 타고 내려가는 과정을 따라가 볼게요. 들여쓰기가 깊어질수록 트리 아래로 내려간 겁니다.

 preorder(1) 이 표본 트리를 타고 내려가는 순서

  preorder(1): 1 방문 → [1]
    preorder(2): 2 방문 → [1, 2]
      preorder(4): 4 방문 → [1, 2, 4]
      preorder(5): 5 방문 → [1, 2, 4, 5]
    preorder(3): 3 방문 → [1, 2, 4, 5, 3]
      preorder(6): 6 방문 → [1, 2, 4, 5, 3, 6]

  최종 방문 순서: 1 → 2 → 4 → 5 → 3 → 6

루트 1을 먼저 찍고, 왼쪽 서브트리(2·4·5)를 통째로 끝낸 뒤, 오른쪽 서브트리(3·6)로 넘어갑니다. 모든 노드를 한 번씩 보니 시간은 O(n)이에요. 공간은 재귀 호출이 트리 높이만큼 쌓이므로 O(h)입니다(h = 트리 높이). 균형 잡힌 트리면 h ≈ log n, 한쪽으로 치우치면 h ≈ n이고요. 재귀 자체는 나중에 별도 시간에 본격적으로 파고드는데, 트리 순회엔 지금 이만큼이면 충분합니다.

🎯 코테에서는 트리 문제의 태반이 순회입니다. "각 노드에서 무언가 하고 자식으로 내려간다"가 뼈대예요. 전위 순회는 "부모를 먼저 처리해야 하는" 일(트리를 위에서 아래로 복사·출력)에 맞습니다.

💡 한 줄 정리

순회는 모든 노드를 한 번씩 방문하는 것이고, 트리가 "루트 + 서브트리들"이라는 재귀 구조라 재귀로 짜면 자연스럽다. 전위 순회는 "나 → 왼쪽 → 오른쪽"으로 루트를 먼저 찍으며, 시간 O(n)·공간 O(h)다.

Step 4: "트리를 훑는 법 ② 중위·후위 순회" — 나를 언제 방문하느냐

전위 순회를 이해했다면 나머지 둘은 거저입니다. 코드가 거의 똑같고, "나(루트)를 언제 찍느냐"만 바뀌거든요. 왼쪽을 오른쪽보다 먼저 보는 건 셋 다 같습니다.

중위 순회(inorder)는 "왼쪽 → 나 → 오른쪽"으로, 나를 가운데에 찍습니다. 후위 순회(postorder)는 "왼쪽 → 오른쪽 → 나"로, 자식을 다 본 뒤 맨 마지막에 나를 찍고요.

# structures/binary_tree.py
def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)


def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

[node.val]이 앞·가운데·뒤 어디에 오느냐만 다르죠. 세 순회를 표본 트리에 돌리면 방문 순서가 이렇게 갈립니다.

셋 다 모든 노드를 한 번씩 보므로 시간 O(n)·공간 O(h)로 똑같습니다. 그럼 왜 셋으로 나눌까요? 처리 순서가 문제마다 다르기 때문이에요.

특히 중위 순회는 오늘 뒤에 배울 이진탐색트리(BST)에서 결정적으로 쓰입니다. BST를 중위 순회하면 값이 오름차순으로 정렬돼 나오거든요. 이 성질이 왜 나오는지는 Step 6·7에서 확인합니다. 후위 순회는 "자식을 다 끝내야 나를 처리할 수 있는" 일에 맞아요. 폴더 용량을 계산할 때 하위 폴더 용량을 다 더한 뒤 상위 폴더 용량이 나오는 것처럼요.

🎯 코테에서는 "BST가 유효한지 검증"하는 문제에 중위 순회가 단골로 나옵니다. 중위 순회 결과가 오름차순이면 올바른 BST죠. 후위 순회는 트리를 안전하게 지우거나(자식부터 지워야 함), 수식 트리를 계산할 때 쓰입니다.

💡 한 줄 정리

전위·중위·후위 순회는 "나(루트)를 언제 방문하느냐"만 다르고, 왼쪽이 오른쪽보다 먼저인 건 같다. 셋 다 O(n)·O(h)이며, 특히 중위 순회는 BST를 정렬된 순서로 뽑아 준다.

Step 5: "재귀 없이 훑기" — 스택으로 반복 순회

Step 3에서 예고한 걸 지킬 시간입니다. 재귀는 사실 컴퓨터가 호출 스택에 노드를 쌓았다 꺼내는 일을 대신해 준 거예요. 그 스택을 우리가 직접 만들면, 재귀 없이 반복문만으로 같은 순회를 낼 수 있습니다. 그보다 앞서 배운 스택이 여기서 정면으로 돌아옵니다.

전위 순회를 스택으로 바꿔 볼게요. 루트를 스택에 넣고, 하나 꺼내 방문한 뒤 그 자식들을 다시 넣습니다. 핵심은 넣는 순서예요. 스택은 나중에 넣은 게 먼저 나오는(LIFO) 구조라, 왼쪽을 먼저 꺼내려면 오른쪽을 먼저, 왼쪽을 나중에 넣어야 합니다.

# structures/binary_tree.py
def preorder_iterative(root):
    if root is None:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right is not None:
            stack.append(node.right)     # 오른쪽을 먼저 넣고
        if node.left is not None:
            stack.append(node.left)      # 왼쪽을 나중에 넣어야 먼저 꺼내진다
    return result

스택이 어떻게 변하는지 한 걸음씩 따라가 봅시다.

 명시적 스택으로 전위 순회 (스택은 나중에 넣은 게 먼저 나온다)

  스택 [1]      → 1 방문, 오른쪽(3)·왼쪽(2) 넣기  → 스택 [3, 2]
  스택 [3, 2]   → 2 방문, 오른쪽(5)·왼쪽(4) 넣기  → 스택 [3, 5, 4]
  스택 [3,5,4]  → 4 방문 (자식 없음)              → 스택 [3, 5]
  스택 [3, 5]   → 5 방문                          → 스택 [3]
  스택 [3]      → 3 방문, 오른쪽(6) 넣기           → 스택 [6]
  스택 [6]      → 6 방문                          → 스택 []

  방문 순서: 1 → 2 → 4 → 5 → 3 → 6  (재귀 전위와 똑같다)

결과가 재귀판과 한 글자도 다르지 않죠. 빅오도 같습니다. 모든 노드를 한 번씩 보니 시간 O(n), 스택에 최대 트리 높이만큼 쌓이니 공간 O(h)예요.

그럼 재귀가 더 짧은데 왜 굳이 반복으로 바꿀까요? 아주 깊은 트리 때문입니다. 파이썬은 재귀 깊이에 기본 한도(약 1000)가 있어서, 노드 수십만 개가 한쪽으로 치우친 트리를 재귀로 순회하면 한도를 넘어 오류가 납니다. 이럴 때 스택으로 바꾸거나, 코테에선 sys.setrecursionlimit으로 한도를 올려요. "재귀가 안전하지 않을 만큼 깊어지면 반복으로"가 실전의 감각입니다.

🎯 코테에서는 트리가 아주 깊을 수 있는 문제(노드 10만 이상, 편향 가능)에서 재귀가 RecursionError로 터지는 경우가 있습니다. 그때 이 반복 순회나 sys.setrecursionlimit(10**6) 한 줄이 해결책이에요. 원리(재귀 = 숨은 스택)를 알면 이 전환이 막히지 않습니다.

💡 한 줄 정리

재귀는 내부적으로 호출 스택에 노드를 쌓았다 꺼내는 것이고, 그 스택을 명시적으로 만들면 반복문으로 같은 순회를 낸다. 전위는 오른쪽·왼쪽 순으로 넣어(LIFO) 왼쪽을 먼저 꺼낸다. 빅오는 재귀와 같은 O(n)·O(h)이고, 아주 깊은 트리에서 재귀 한도를 피하는 안전장치가 된다.

Step 6: "정렬된 트리" — BST 삽입

지금까지의 이진트리는 값을 아무 데나 넣었습니다. 여기에 규칙 하나를 걸면, 검색이 폭발적으로 빨라지는 특별한 트리가 됩니다. 이진탐색트리(Binary Search Tree, BST)예요.

규칙은 단 하나입니다. 모든 노드에서, 왼쪽 서브트리의 값들은 나보다 작고, 오른쪽 서브트리의 값들은 나보다 크다. 노드 모양은 앞의 TreeNode를 그대로 씁니다(BST는 규칙만 다른 이진트리예요). 값을 넣을 때 이 규칙을 지키며 자리를 찾아 내려갑니다. 작으면 왼쪽, 크면 오른쪽으로 가다가 빈 자리(None)에 닿으면 거기에 새 노드를 답니다.

# structures/bst.py
def bst_insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    elif val > root.val:
        root.right = bst_insert(root.right, val)
    # val == root.val 이면 아무것도 안 함(중복 무시)
    return root

5, 3, 8, 1, 4, 7, 9를 차례로 넣으면 어떻게 자리를 잡는지 따라가 볼게요.

 BST 만들기 — 5, 3, 8, 1, 4, 7, 9 를 차례로 (작으면 왼쪽, 크면 오른쪽)

  5 를 뿌리로.  3<5 → 왼쪽.  8>5 → 오른쪽.
  1<5 → 왼쪽, 1<3 → 3의 왼쪽.   4<5 → 왼쪽, 4>3 → 3의 오른쪽.
  7>5 → 오른쪽, 7<8 → 8의 왼쪽.  9>5 → 오른쪽, 9>8 → 8의 오른쪽.

        5
       / \
      3   8
     / \ / \
    1  4 7  9

넣은 순서는 뒤죽박죽이었지만, 규칙대로 내려가니 값이 크기순으로 자리를 잡았습니다. 여기서 Step 4의 예고가 회수돼요. 이 트리를 중위 순회(왼 → 나 → 오)하면 [1, 3, 4, 5, 7, 8, 9], 정확히 오름차순이 나옵니다. "왼쪽이 나보다 작다"는 규칙이 곧 "왼쪽을 먼저 찍으면 작은 값부터 나온다"이기 때문이죠.

새 값을 넣는 비용은 빈 자리를 찾아 내려간 길이, 즉 트리 높이만큼입니다. 균형 잡힌 트리면 평균 O(log n)이에요. 참고로 같은 값이 또 들어오면 위 코드는 무시합니다(중복 없는 집합처럼). 파이썬에는 균형 BST 표준 라이브러리가 없어서, 실전에서 "정렬 상태를 유지하며 넣고 찾기"가 필요하면 보통 정렬 리스트와 bisect(정렬된 배열을 절반씩 탐색하는 도구, 나중에 배웁니다)를 씁니다. BST의 진짜 값어치는 다음 Step에서 볼 "절반씩 버리며 찾는" 사고를 트리로 익히는 데 있어요.

🎯 코테에서는 BST에 값을 삽입하거나, 주어진 트리가 올바른 BST인지 검증하는 문제가 나옵니다. "왼쪽 < 나 < 오른쪽" 규칙 한 줄이 삽입·검증·탐색을 전부 관통해요.

💡 한 줄 정리

BST는 "왼쪽 서브트리는 나보다 작고, 오른쪽 서브트리는 나보다 크다"는 규칙을 건 이진트리다. 값을 넣을 때 작으면 왼쪽·크면 오른쪽으로 내려가 빈 자리에 단다(평균 O(log n)). 중위 순회하면 오름차순으로 나온다.

Step 7: "절반씩 버리며 찾는다" — BST 탐색과 균형의 함정

BST 규칙의 보상을 받을 시간입니다. 값을 찾을 때, 규칙 덕분에 한 노드에서 한쪽으로만 내려가면 돼요. 찾는 값이 지금 노드보다 작으면 오른쪽은 통째로 버리고 왼쪽으로, 크면 왼쪽을 버리고 오른쪽으로. 매 걸음 후보의 절반이 사라집니다.

# structures/bst.py
def bst_search(root, val):
    node = root
    while node is not None:
        if val == node.val:
            return True
        node = node.left if val < node.val else node.right
    return False

이 "절반씩 버린다"가 바로 이진 탐색(binary search)의 사고예요. 정렬된 데이터를 절반씩 좁혀 O(log n)에 찾는 이 발상은, 나중에 정렬된 배열 위에서 본격적으로 다시 배웁니다. BST는 그 사고를 트리 모양으로 구현한 거고요. 원소가 100만 개여도 균형 잡힌 BST면 약 20번(log₂ 100만 ≈ 20) 만에 찾습니다.

핵심 연산의 빅오를 표로 정리하면 이렇습니다.

그런데 최악 O(n)이 눈에 띄죠. 여기가 BST의 함정입니다. 평균 O(log n)은 트리가 좌우로 균형 잡혔을 때(높이 ≈ log n) 이야기예요. 만약 값을 정렬된 순서로 넣으면 어떻게 될까요?

 같은 값 1,2,3,4,5 라도 넣는 순서에 따라 모양이 갈린다

 [균형]  3, 2, 4, 1, 5 처럼 가운데부터 넣으면
        3
       / \
      2   4
     /     \
    1       5
   → 높이 2, 탐색은 절반씩 버려 O(log n)

 [치우침]  1, 2, 3, 4, 5 를 정렬 순서로 넣으면
    1
     \
      2
       \
        3
         \
          4
           \
            5
   → 높이 4, 한쪽으로만 자라 사실상 연결 리스트, 탐색 O(n)

정렬된 순서로 넣으면 매번 오른쪽으로만 내려가, 트리가 한쪽으로 자라 일자가 됩니다. 이건 사실상 연결 리스트라 탐색이 O(n)으로 무너져요. "1초에 약 1억 연산" 잣대로 보면, 100만 원소를 균형 트리에선 20번에 찾지만 일자 트리에선 최악 100만 번을 봐야 합니다. 당락이 갈리죠.

⚠️ 이 최악을 막으려고, 실무의 트리는 스스로 균형을 맞추는 변형을 씁니다. 자바의 TreeMap이 쓰는 레드-블랙 트리, 데이터베이스 인덱스의 B-트리가 그것이에요. 넣고 뺄 때마다 좌우 높이를 자동으로 맞춰 높이를 항상 log n 근처로 유지합니다. 지난 시간에 흘려 둔 이야기 기억나나요? 자바 HashMap이 한 칸의 체인이 너무 길어지면 그 체인을 균형 트리로 바꿔 최악을 O(log n)으로 막는다고 했죠. 그 균형 트리가 바로 이런 자가 균형 BST입니다.

💡 한 줄 정리

BST 탐색은 "작으면 왼쪽, 크면 오른쪽"으로 매 걸음 후보의 절반을 버려 평균 O(log n)이다(이진 탐색의 트리판). 단 정렬된 순서로 넣으면 한쪽으로 자라 일자가 되어 최악 O(n)으로 무너진다. 그래서 실무는 자가 균형 트리로 높이를 log n 근처로 지킨다.

Step 8: "트리로 답 구하기" — 높이·노드 수·지름

마지막으로, 트리를 순회하며 답을 계산하는 패턴을 봅니다. 핵심 발상은 하나예요. "자식들에게 답을 물어 받아서, 그걸 모아 내 답을 만든다." 후위 순회(자식 먼저, 나 나중)의 정신이죠.

가장 단순한 예가 노드 개수와 높이입니다.

# structures/binary_tree.py
def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)


def tree_height(node):
    if node is None:
        return -1
    return 1 + max(tree_height(node.left), tree_height(node.right))

count_nodes는 "나 하나 + 왼쪽 개수 + 오른쪽 개수"로 셉니다. tree_height는 "1 + 자식 중 더 높은 쪽"이고요. 빈 트리를 -1, 리프를 0으로 두면 이 식이 깔끔하게 맞습니다.

⚠️ 높이의 정의는 문제마다 갈립니다. 여기선 간선 수 기준(빈 트리 -1, 리프 0)이지만, LeetCode의 "최대 깊이"(문제 104)는 노드 수로 세서 리프를 1, 빈 트리를 0으로 봐요. 둘 다 맞습니다. 코테에선 그 문제가 어느 정의를 쓰는지 예시로 먼저 확인하세요.

이제 조금 더 나아간 문제, 트리의 지름(diameter)입니다. 지름이란 트리에서 임의의 두 노드를 잇는 가장 긴 경로의 간선 수예요. 표본 트리에서 가장 긴 경로는 4 → 2 → 1 → 3 → 6으로 간선 4개입니다.

 트리의 지름 = 두 노드를 잇는 가장 긴 경로 (표본 트리)

        1
       / \
      2   3
     / \   \
    4   5   6

  가장 긴 경로: 4 → 2 → 1 → 3 → 6  (간선 4개)
  요령: 각 노드에서 '왼쪽 아래로 가장 먼 깊이 + 오른쪽 아래로 가장 먼 깊이'가
        그 노드를 지나는 최장 경로. 1 에서 왼쪽 2간선 + 오른쪽 2간선 = 4.

핵심은 "각 노드를 지나는 가장 긴 경로 = 왼쪽 깊이 + 오른쪽 깊이"라는 점입니다. 그래서 한 번의 후위 순회로 각 노드의 깊이를 아래에서 위로 올려보내면서, 그때그때 "왼쪽 + 오른쪽"으로 지름 후보를 갱신하면 됩니다.

def tree_diameter(root):
    best = 0

    def depth(node):        # 이 노드 아래로 가장 먼 리프까지의 간선 수(없으면 -1)
        nonlocal best
        if node is None:
            return -1
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, (left + 1) + (right + 1))   # 이 노드를 지나는 경로 길이
        return 1 + max(left, right)

    depth(root)
    return best

각 노드에서 자식의 깊이(left·right)를 받아, 그 노드를 지나는 경로 길이로 best를 갱신하고, 자기 깊이는 위로 올려보냅니다. 모든 노드를 한 번씩만 보므로 O(n)이에요. 만약 노드마다 높이를 매번 따로 구하면 O(n²)로 느려지는데, 깊이를 올려보내며 한 번에 처리해 O(n)으로 줄인 겁니다. 이렇게 자식의 결과를 모아 부모의 답을 키우는 방식이, 나중에 배울 동적 계획법(트리 DP)의 맛보기예요.

이걸로 오늘의 두 트랙이 마무리됩니다. 트리를 직접 재귀로 순회해 원리를 봤고, 실전 코테에서도 이 재귀 몇 줄을 거의 그대로 쓰거나 트리를 딕셔너리로 표현합니다. 원리를 손으로 훑어 본 사람이, 문제에서 트리가 나왔을 때 "순회로 풀까, 규칙(BST)으로 풀까"를 곧장 판단해요.

🎯 코테에서는 트리의 지름(LeetCode 543), 최대 깊이(104), 노드 수(222)가 단골입니다. 전부 "자식의 결과를 모아 내 답을 만드는" 후위 순회 패턴이에요. 이 패턴 하나로 트리 계산 문제의 상당수가 풀립니다.

💡 한 줄 정리

트리로 답을 구하는 패턴은 "자식들에게 답을 물어 받아 내 답을 만든다"(후위 순회)이다. 노드 수·높이는 한 줄 재귀로, 트리의 지름은 깊이를 올려보내며 한 번의 순회로 O(n)에 구한다. 이 "자식 결과를 모아 부모 답"이 트리 DP의 맛보기다.

마무리

오늘은 데이터가 가지를 치는 첫 그릇, 트리를 만들었습니다. 노드에 왼쪽·오른쪽 두 포인터를 달아 이진트리를 세우고, 세 가지 순회로 훑고, "왼쪽은 작게 오른쪽은 크게" 규칙을 건 BST로 평균 O(log n) 탐색까지 왔어요. 지난 시간 흘려 둔 "노드는 다음 하나"가, 오늘 "노드는 자식 여럿"으로 넓어졌습니다.

오늘 배운 핵심 세 가지

• 💡 하나 — 트리는 노드가 자식 둘(왼쪽·오른쪽)을 가리키는 비선형 구조다. 연결 리스트의 노드에 포인터를 하나 더 단 확장이고, 그래서 데이터가 한 줄이 아니라 가지를 친다. 노드 접근 O(1), 트리 구성 O(n).
• 💡 둘 — 순회는 "나를 언제 방문하느냐"로 전위·중위·후위가 갈린다. 트리가 재귀 구조라 재귀로 짜면 자연스럽고(O(n)·O(h)), 재귀의 숨은 스택을 직접 꺼내면 반복 순회가 된다. 중위 순회는 BST를 정렬된 순서로 뽑아 준다.
• 💡 셋 — BST는 "왼쪽 < 나 < 오른쪽" 규칙으로 절반씩 버리며 평균 O(log n)에 찾는다. 단 정렬된 순서로 넣어 한쪽으로 치우치면 일자가 되어 최악 O(n)으로 무너진다. 그래서 균형이 관건이고, 실무는 자가 균형 트리로 높이를 지킨다.

다음 시간 예고

다음 시간엔 트리 중에서도 아주 특별한 모양을 다룹니다. 완전 이진트리(complete binary tree) — 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진 트리예요. 이 규칙적인 모양 덕분에, 놀랍게도 포인터 없이 배열 한 장에 트리를 통째로 담을 수 있습니다. 이걸 이용해 최댓값(또는 최솟값)을 O(log n)에 뽑아 내는 자료구조가 힙(heap)이고, 그 위에 세운 게 우선순위 큐예요. 오늘 배운 트리 높이와 O(log n)의 감각이 그대로 이어지니, "트리를 배열에 어떻게 담지?"를 한번 상상해 보고 오세요.

과제

오늘 배운 트리를 직접 손으로 다뤄 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 리프 노드의 개수

이진트리의 루트가 주어질 때, 리프 노드(자식이 하나도 없는 노드)의 개수를 세는 함수를 작성하세요. 예를 들어 오늘의 표본 트리(루트 1)라면 리프는 4·5·6으로 3개입니다.

힌트는 오늘 본 count_nodes예요. 거기선 "나 하나 + 왼쪽 + 오른쪽"으로 모든 노드를 셌죠. 여기선 "나"를 셀지 말지가 조건에 달렸습니다. 왼쪽도 오른쪽도 없는 노드일 때만 1을 세도록 바꿔 보세요. 시간·공간 복잡도도 빅오로 적으세요. (트리 순회의 가장 기본 유형입니다.)

[응용] 좌우 대칭 트리 판별

이진트리의 루트가 주어질 때, 그 트리가 좌우로 대칭(거울에 비친 듯)인지 판별하는 함수를 작성하세요(대칭이면 True). 예를 들어 루트의 왼쪽 서브트리와 오른쪽 서브트리가 서로의 거울상이면 대칭입니다.

핵심은 "한 트리를 혼자 순회"하는 게 아니라 두 서브트리(왼쪽·오른쪽)를 동시에, 거울처럼 마주 보며 비교하는 거예요. 왼쪽의 왼쪽 자식과 오른쪽의 오른쪽 자식을, 왼쪽의 오른쪽 자식과 오른쪽의 왼쪽 자식을 짝지어 비교합니다. 두 노드를 받아 "값이 같고, 바깥끼리·안쪽끼리 거울로 같은가"를 재귀로 따져 보세요. 시간·공간 복잡도를 빅오로 적으세요. (LeetCode "Symmetric Tree" 패턴입니다.)

[심화] 올바른 이진탐색트리인지 검증

이진트리의 루트가 주어질 때, 그 트리가 올바른 BST인지(모든 노드에서 왼쪽 < 나 < 오른쪽 규칙을 지키는지) 검증하는 함수를 작성하세요.

오늘 Step 4·6에서 "BST를 중위 순회하면 오름차순으로 나온다"를 봤죠. 그걸 뒤집으면 검증이 됩니다. 중위 순회 결과가 엄격히 오름차순이면 올바른 BST예요. 중위 순회로 값들을 뽑은 뒤, 이웃한 값이 항상 앞 < 뒤인지 확인해 보세요. 시간·공간 복잡도를 빅오로 적고, "각 노드가 지켜야 할 값의 범위(min, max)를 물려주며 검증하는" 다른 풀이도 가능한지 생각해 보세요. (LeetCode "Validate Binary Search Tree" 패턴입니다.)

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. BST는 평균 O(log n)인데, 왜 "최악 O(n)"을 늘 함께 적을까?

BST의 삽입·탐색은 보통 평균 O(log n)이지만, 책과 면접관은 꼭 "최악 O(n)"을 함께 묻습니다. 어떤 상황에서 BST가 O(n)으로 무너질까요? 값을 정렬된 순서로 넣어 한쪽으로 치우친 경우를 떠올려 보세요. 지난 시간의 해시가 "충돌이 몰리면 최악 O(n)"이었던 것과 닮은 구조입니다. 그리고 이 최악을 막는 자가 균형 트리(레드-블랙 트리·AVL 트리·B-트리)가 무엇을 자동으로 하는지, 왜 데이터베이스 인덱스가 그런 트리를 쓰는지도 함께 정리해 보세요.

2. 트리 순회, 재귀로 짤까 반복으로 짤까?

같은 순회를 재귀로도, 명시적 스택 반복으로도 짤 수 있었습니다. 재귀는 짧고 트리 구조를 그대로 옮겨 읽기 쉽지만, 아주 깊은 트리에선 호출 스택 한도를 넘어 오류가 날 수 있어요. 반복은 길지만 그 한도에서 자유롭고요. 어떤 상황에 어느 쪽을 고를지, 그리고 "재귀가 사실은 스택을 쓰고 있다"는 사실이 이 선택에서 무엇을 알려 주는지 생각해 보세요. 코테에서 sys.setrecursionlimit을 올리는 것과 반복으로 바꾸는 것은 각각 어떤 트레이드오프가 있을까요?

3. 연결 리스트는 트리의 특수형, 트리는 그래프의 특수형 — 자료구조의 계보

오늘 "자식이 하나뿐인 트리 = 연결 리스트", "치우친 BST = 일자 = 연결 리스트"를 봤습니다. 또 트리는 "사이클 없이 연결된 그래프"라고도 했죠. 이렇게 자료구조들이 서로의 특수형·일반형으로 이어진다는 걸, 지금까지 배운 것(배열·연결 리스트·해시·트리)을 돌아보며 정리해 보세요. 그리고 "직접 구현으로 원리, 내장으로 실전"이라는 두 트랙이 다음 카테고리(힙·그래프)에서 어떻게 이어질지도 그려 보세요 — 힙은 트리를 배열에 담고, 그래프는 노드와 포인터를 더 자유롭게 잇습니다. 오늘의 노드·포인터·순회가 그 바닥에 어떻게 깔리는지가 이 질문의 핵심이에요.