[알고리즘] 재귀로 이진 트리 순회하기 (전위/중위/후위)

코딩테스트 합격자 되기(파이썬) 책의 '트리 순회' 문제를 풀면서 정리한 재귀 동작 원리. 재귀가 왜 헷갈리는지, ret += 재귀호출() 한 줄이 실제로 어떻게 동작하는지 추적해봤다.

---

1. 재귀(Recursion)의 핵심 구조

핵심 아이디어

종료 조건 → 현재 할 일 → 더 작은 문제로 재귀 호출

함수가 자기 자신을 다시 호출하면서 문제를 점점 작게 쪼개다가, 더 이상 쪼갤 수 없는 지점(종료 조건)에서 멈추는 방식이다.

기본 구조

def recursive(현재상태):
    # 1. 종료조건 먼저!
    if 종료조건:
        return 기저값

    # 2. 현재 할 일
    현재처리()

    # 3. 더 작은 문제로 재귀호출
    return recursive(더작은상태)

ret이 쌓이는 원리: "전화 돌리기"

재귀에서 가장 헷갈리는 부분은 보통 ret += 재귀호출(...) 같은 코드다. 이건 "왼쪽 자식이 자기 할 일을 다 끝내고 결과를 올려주면, 그걸 내 ret에 붙이는 것" 으로 이해하면 된다.

[1단계] preorder(nodes, 0) 호출됨
        ret = "1 "
        ret += preorder(nodes, 1)  ← 여기서 멈추고 기다림
                ret = "2 "
                ret += preorder(nodes, 3) ← 멈추고 기다림
                        idx(3) >= len(3) → return ""
                ret = "2 " + "" = "2 "
                return "2 "
        ret = "1 " + "2 " = "1 2 "

각 함수 호출은 독립적으로 실행되며, 자기 자식 함수가 결과를 반환할 때까지 기다렸다가(pause) 그 결과를 받아서 자신의 ret에 이어 붙인다. 함수 안에서 호출한 함수가 완전히 끝나야 비로소 그 결과가 += 로 합쳐진다.

=과 +=을 섞어 쓰는 이유

def inorder(nodes, idx):
    if idx < len(nodes):
        ret = inorder(nodes, idx*2+1)   # 처음엔 = (변수를 새로 만듦)
        ret += str(nodes[idx]) + " "    # 이후엔 += (이미 있는 값에 이어붙임)
        ret += inorder(nodes, idx*2+2)
        return ret
    else:
        return ""

첫 줄은 ret이라는 변수가 아직 존재하지 않으므로 =로 처음 값을 만들어줘야 한다. ret += "..."는 사실 ret = ret + "..."의 줄임 표현인데, ret이 아직 없는 상태에서 +=를 쓰면 "있지도 않은 변수에 더하라"는 뜻이 되어 에러가 난다.

---

2. 배열로 표현한 이진 트리

nodes = [1, 2, 3, 4, 5, 6, 7]이 있을 때, 인덱스 idx를 기준으로 자식 노드 위치가 정해진다.

• 왼쪽 자식 = idx * 2 + 1
• 오른쪽 자식 = idx * 2 + 2

            1 (idx=0)
          /           \
     2 (idx=1)       3 (idx=2)
     /      \         /      \
4(idx=3) 5(idx=4) 6(idx=5) 7(idx=6)

---

3. 전위/중위/후위 순회

세 가지 순회 코드

def preorder(nodes, idx):
    if idx < len(nodes):
        ret = str(nodes[idx]) + " "       # 나 먼저
        ret += preorder(nodes, idx*2+1)   # 왼쪽
        ret += preorder(nodes, idx*2+2)   # 오른쪽
        return ret
    else:
        return ""

def inorder(nodes, idx):
    if idx < len(nodes):
        ret = inorder(nodes, idx*2+1)     # 왼쪽 먼저
        ret += str(nodes[idx]) + " "      # 나
        ret += inorder(nodes, idx*2+2)    # 오른쪽
        return ret
    else:
        return ""

def postorder(nodes, idx):
    if idx < len(nodes):
        ret = postorder(nodes, idx*2+1)   # 왼쪽
        ret += postorder(nodes, idx*2+2)  # 오른쪽
        ret += str(nodes[idx]) + " "      # 나 마지막!
        return ret
    else:
        return ""

세 순회의 차이는 "나를 추가하는 시점" 단 한 줄

순회 나를 추가하는 시점 결과 (nodes=[1~7])

전위(preorder)	왼쪽/오른쪽 전에	1 2 4 5 3 6 7
중위(inorder)	왼쪽 후, 오른쪽 전	4 2 5 1 6 3 7
후위(postorder)	왼쪽/오른쪽 후에	4 5 2 6 7 3 1

str(nodes[idx])를 더하는 코드 한 줄의 위치만 바뀌는 것이고, 나머지 구조는 완전히 동일하다.

중위 순회 전체 흐름 (왜 "4 2 5"와 "1"이 따로 합쳐지는가)

inorder(0)의 ret은 한 번에 채워지지 않고, 세 단계에 걸쳐 순서대로 채워진다.

inorder(0) 의 ret 변수

1단계: ret = inorder(1)  →  ret = "4 2 5 "   (왼쪽 가지 전체가 채워서 반환)
2단계: ret += "1 "        →  ret = "4 2 5 1 " (나 자신 추가)
3단계: ret += inorder(2)  →  ret = "4 2 5 1 6 3 7 " (오른쪽 가지 전체가 채워서 반환)

inorder(1)과 inorder(2)는 완전히 독립적인 함수 호출이다. 트리에서 왼쪽 가지 전체는 inorder(1)이 혼자 책임지고, 오른쪽 가지 전체는 inorder(2)가 혼자 책임진다. 둘을 합치고 자기 자신(1)을 끼워 넣는 일은 inorder(0)만의 책임이다.

---

4. 시간복잡도

N은 노드의 개수다. 전위, 중위, 후위 연산 모두 각 노드를 한 번씩만 방문하므로 시간복잡도는 O(N) 이다.

---

5. 재귀, 외워야 할까 이해해야 할까

패턴은 이해로 외워지는 것이지, 무작정 암기하거나 매번 백지에서 창작하는 게 아니다.

코딩테스트에서 트리 순회 자체보다 더 자주 나오는 건 DFS 탐색과 백트래킹이며, 둘 다 재귀의 같은 틀(종료조건 → 처리 → 재귀호출)을 응용한다. 따라서 트리 순회를 통해 이 틀이 왜 동작하는지 원리를 이해해두면, 이후 DFS·백트래킹 문제에서 패턴을 변형해 적용하는 응용력으로 이어진다.