트리 자료구조: 이진 트리, 이진 탐색 트리(BST), 전위·중위·후위 순회
이 글의 핵심
트리 문제는 대부분 왼쪽 서브트리와 오른쪽 서브트리의 답을 합치는 재귀로 풀립니다. 순회 순서에 따라 결과가 어떻게 달라지는지, BST를 중위 순회하면 왜 정렬된 순서가 나오는지 짚고, 문제를 만났을 때 어떤 순회를 쓸지 고르는 접근법과 추천 문제를 정리합니다.
시리즈 안내
#04 | 📋 전체 목차 | 이전: #03 해시 테이블 · 다음: #05 그래프
들어가며
계층 구조를 표현하는 자료구조
트리는 계층 구조를 표현하는 자료구조입니다. 파일 시스템, DOM, 조직도 등 모두 트리입니다.
그래프 관점에서 보면 트리는 사이클이 없고 모든 노드가 연결된 그래프입니다. 노드가 n개면 간선은 정확히 n-1개이고, 두 노드 사이의 경로는 하나뿐입니다. 이 “경로가 유일하다”는 성질 덕분에 트리 문제는 방문 여부를 따로 기록하지 않아도 되고(부모로 되돌아가지만 않으면 됨), 한 노드를 기준으로 문제를 왼쪽·오른쪽 서브트리라는 서로 겹치지 않는 작은 문제로 나눌 수 있습니다. 트리 문제 대부분이 재귀로 자연스럽게 풀리는 이유가 여기에 있습니다.
트리 기본 개념
용어
1 ← 루트(Root)
/ \
2 3 ← 자식(Child)
/ \
4 5 ← 리프(Leaf)
- 노드(Node): 1, 2, 3, 4, 5
- 간선(Edge): 노드를 연결하는 선
- 부모(Parent): 2의 부모는 1
- 자식(Child): 1의 자식은 2, 3
- 형제(Sibling): 2와 3
- 깊이(Depth): 루트부터 거리 (4의 깊이 = 2)
- 높이(Height): 리프까지 최대 거리 (트리 높이 = 2)
- 레벨(Level): 같은 깊이의 노드들깊이와 높이는 간선 수로 셀지, 노드 수로 셀지가 자료마다 다르다는 점을 주의해야 합니다. 위 정의는 간선 수 기준이라 루트만 있는 트리의 높이가 0이고, 이 그림의 높이는 2입니다. 반면 LeetCode의 “Maximum Depth”처럼 노드 수로 세는 문제에서는 같은 트리의 답이 3입니다. 아래 4장의 max_depth도 노드 수 기준이라 빈 트리에 0, 노드 하나에 1을 돌려줍니다. 문제를 풀 때 기저 조건의 반환값(0인지 -1인지)이 이 정의에 따라 달라지므로, 문제의 예시로 한 번 확인하고 시작하는 것이 좋습니다.
Python 구현
아래는 값(val)과 왼쪽·오른쪽 자식 포인터를 갖는 노드를 정의하며, 루트에서 아래로 가지를 뻗어 연결하는 예입니다. 조직도나 가계도처럼 한 부모 아래에 자식이 달리는 구조를 코드로 만든 것입니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)LeetCode는 이 TreeNode 정의를 그대로 주고 루트 노드를 인자로 넘기지만, 백준이나 프로그래머스는 “N개의 간선이 주어진다”처럼 입력을 텍스트로 줍니다. 이때는 노드 객체를 만들기보다 딕셔너리나 리스트로 표현하는 편이 간단합니다. 백준 1991번처럼 노드 이름과 왼쪽·오른쪽 자식이 주어지면 tree = {'A': ('B', 'C'), ...}로, 11725번처럼 부모·자식 구분 없이 간선만 주어지면 인접 리스트 graph[u].append(v)로 저장하고 루트에서 탐색하며 부모를 정합니다. 이진 트리가 아니라 자식이 여러 개인 일반 트리라면 children 리스트를 두면 됩니다.
트리 순회
순회는 모든 노드를 정확히 한 번씩 방문하는 순서를 정한 것으로, 이름은 부모를 언제 방문하느냐로 붙습니다. 부모를 먼저(pre), 가운데(in), 나중(post)에 방문하는 것이 차이의 전부이고, 왼쪽을 오른쪽보다 먼저 방문한다는 점은 세 방식 모두 같습니다.
전위 순회 (Preorder)
부모 → 왼쪽 → 오른쪽 순서로 방문합니다:
def preorder(node):
# 기저 조건: 노드가 없으면 빈 리스트 반환
if not node:
return []
# 전위 순회 순서:
# 1. 부모 노드 먼저 방문: [node.val]
# 2. 왼쪽 서브트리 순회: preorder(node.left)
# 3. 오른쪽 서브트리 순회: preorder(node.right)
return [node.val] + preorder(node.left) + preorder(node.right)
# 트리 구조:
# 1
# / \
# 2 3
# / \
# 4 5
#
# 순회 과정:
# 1. 노드 1 방문 → [1]
# 2. 왼쪽(2) 이동 → [1, 2]
# 3. 왼쪽(4) 이동 → [1, 2, 4]
# 4. 4는 리프 → 백트랙
# 5. 오른쪽(5) 이동 → [1, 2, 4, 5]
# 6. 백트랙 후 오른쪽(3) → [1, 2, 4, 5, 3]
#
# 결과: [1, 2, 4, 5, 3]전위 순회 활용:
- 트리 복사 (부모부터 생성)
- 트리 직렬화 (파일 저장)
- 수식 트리의 전위 표기법 (Prefix notation)
위 재귀 구현은 읽기 쉽지만 두 가지 비용이 숨어 있습니다. 첫째, [node.val] + preorder(...) + preorder(...)는 호출마다 새 리스트를 만들어 이어 붙이므로, 한쪽으로 치우친 트리에서는 전체 시간이 O(n²)까지 늘어납니다. 결과 리스트 하나를 인자로 넘기며 result.append(node.val)로 채우는 방식이 O(n)입니다. 둘째, Python의 기본 재귀 한도는 1,000 정도라서 노드가 수만 개인 편향 트리에서는 RecursionError: maximum recursion depth exceeded가 납니다. 코딩 테스트에서 노드 수가 10⁵ 규모인 트리 문제를 재귀로 풀면 이 에러가 자주 나는데, sys.setrecursionlimit(10**6)으로 한도를 올리거나 아래처럼 스택을 쓰는 반복문으로 바꾸는 것이 해결책입니다. 한도를 올려도 채점 환경의 실제 스택 메모리가 부족하면 런타임 에러가 날 수 있어, 깊이가 매우 깊을 수 있는 문제라면 반복문이 더 안전합니다.
반복문 구현 (스택 사용):
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root] # 스택에 루트 추가
while stack:
# 스택에서 노드 꺼내기 (LIFO)
node = stack.pop()
result.append(node.val) # 방문
# 오른쪽 먼저 push (나중에 pop)
if node.right:
stack.append(node.right)
# 왼쪽 나중에 push (먼저 pop)
if node.left:
stack.append(node.left)
return result스택은 나중에 넣은 것이 먼저 나오므로, 왼쪽을 먼저 방문하려면 오른쪽을 먼저 넣어야 합니다. 이 순서를 반대로 하면 부모 → 오른쪽 → 왼쪽 순서가 되는데, 이 결과를 뒤집으면 왼쪽 → 오른쪽 → 부모, 즉 후위 순회가 됩니다. 반복문 후위 순회를 간단히 구현할 때 자주 쓰는 방법입니다.
중위 순회 (Inorder)
왼쪽 → 부모 → 오른쪽:
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
# 결과: [4, 2, 5, 1, 3]
# BST에서는 오름차순!중위 순회는 이진 트리에서만 의미가 분명합니다. 자식이 여러 개인 일반 트리에서는 부모를 “가운데”에 둘 기준이 없기 때문입니다. 수식 트리를 중위 순회하면 우리가 평소 쓰는 a + b * c 형태의 중위 표기법이 나오지만, 괄호 정보가 사라지므로 연산 순서를 보존하려면 서브트리마다 괄호를 붙여 출력해야 합니다. BST에서 “k번째로 작은 값”을 찾는 문제는 중위 순회를 하다가 k번째 방문에서 멈추면 되므로, 전체를 정렬할 필요가 없습니다.
후위 순회 (Postorder)
왼쪽 → 오른쪽 → 부모:
def postorder(node):
if not node:
return []
return postorder(node.left) + postorder(node.right) + [node.val]
# 결과: [4, 5, 2, 3, 1]후위 순회는 자식을 모두 처리한 뒤 부모를 처리하므로, 자식의 결과를 모아 부모의 답을 만드는 문제에 맞습니다. 서브트리 크기, 트리 높이, 디렉토리 전체 용량 계산이 모두 이 구조이고, 4장의 max_depth도 사실상 후위 순회입니다. 트리를 메모리에서 해제할 때도 자식을 먼저 지워야 부모의 포인터가 사라지기 전에 자식에 접근할 수 있으므로 후위 순서를 씁니다.
레벨 순회 (Level Order)
BFS 사용:
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 결과: [1, 2, 3, 4, 5]레벨 순회는 큐를 쓰는 BFS라서 루트에서 가까운 노드부터 방문합니다. 큐로 list를 쓰고 pop(0)을 하면 앞의 원소를 지울 때마다 나머지를 한 칸씩 당기느라 O(n)이 걸려 전체가 O(n²)이 되므로, 반드시 deque의 popleft()(O(1))를 써야 합니다.
“레벨별로 묶어서 반환하라”는 문제(LeetCode 102)에서는 위 코드처럼 한 리스트에 모두 담으면 레벨 경계를 알 수 없습니다. 반복문 시작 시점의 len(queue)가 곧 현재 레벨의 노드 수라는 점을 이용해, 그 개수만큼만 꺼내 한 레벨 리스트를 만들고 다음 반복으로 넘어가면 됩니다. 트리의 오른쪽에서 보이는 노드, 레벨별 평균, 지그재그 순회 같은 변형 문제도 모두 이 “레벨 단위 처리” 패턴으로 풉니다.
이진 탐색 트리 (BST)
BST 규칙
왼쪽 < 부모 < 오른쪽:
5
/ \
3 7
/ \ / \
2 4 6 8
중위 순회: [2, 3, 4, 5, 6, 7, 8] (정렬됨!)BST 규칙은 부모와 바로 아래 자식 사이의 관계가 아니라 서브트리 전체에 대한 조건입니다. 왼쪽 서브트리의 모든 값이 부모보다 작아야 합니다. 이 점을 놓쳐서 “올바른 BST인지 확인하라”(LeetCode 98) 문제를 각 노드와 두 자식만 비교해 풀면 틀립니다. 예를 들어 루트 5의 왼쪽 자식 3의 오른쪽에 6이 있으면, 3 < 6이라 부모-자식 비교는 통과하지만 6이 루트 5보다 크므로 BST가 아닙니다. 재귀하면서 허용 범위 (low, high)를 함께 넘기거나, FAQ에 적은 것처럼 중위 순회 결과가 엄격하게 증가하는지 확인해야 합니다.
BST 삽입
BST의 규칙을 유지하며 새 값을 삽입합니다:
def insert_bst(root, val):
# 기저 조건: 빈 자리를 찾으면 새 노드 생성
if not root:
return TreeNode(val)
# BST 규칙: 왼쪽 < 부모 < 오른쪽
if val < root.val:
# val이 현재 노드보다 작으면 왼쪽 서브트리에 삽입
root.left = insert_bst(root.left, val)
else:
# val이 현재 노드보다 크거나 같으면 오른쪽 서브트리에 삽입
# (중복 허용 시 오른쪽에 삽입)
root.right = insert_bst(root.right, val)
# 현재 노드 반환 (재귀 호출 시 부모에게 연결)
return root
# 사용 예시
root = TreeNode(5) # 루트 노드 생성
root = insert_bst(root, 3) # 5보다 작으므로 왼쪽
root = insert_bst(root, 7) # 5보다 크므로 오른쪽
root = insert_bst(root, 2) # 3보다 작으므로 3의 왼쪽
# 결과 트리:
# 5
# / \
# 3 7
# /
# 2
# 삽입 과정 (val=2 삽입):
# 1. root(5): 2 < 5 → 왼쪽으로 # 2. node(3): 2 < 3 → 왼쪽으로 # 3. None: 빈 자리 → TreeNode(2) 생성
# 4. 재귀 반환: 3.left = TreeNode(2)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때
# - 최악: O(n) - 한쪽으로 치우친 트리일 때 (예: 1→2→3→4→5)root.left = insert_bst(root.left, val)처럼 재귀 결과를 다시 대입하는 구조가 핵심입니다. 빈 자리에 도달하면 새 노드를 반환하고, 그 위의 호출들은 자기 자신을 반환하므로 경로상의 연결은 그대로 유지되면서 마지막 한 칸만 새 노드로 채워집니다. 대입을 빠뜨리고 insert_bst(root.left, val)만 호출하면 새 노드가 어디에도 연결되지 않아 조용히 사라집니다.
최악의 경우가 생기는 조건은 생각보다 흔합니다. 이미 정렬된 데이터를 순서대로 삽입하면 매번 오른쪽 끝에 붙어서 트리가 연결 리스트가 됩니다. 1부터 10만까지 순서대로 넣으면 높이가 10만인 트리가 되어, 삽입 전체가 O(n²)이고 재귀 구현은 앞에서 말한 재귀 한도에 걸립니다. 실무에서 쓰는 BST가 AVL 트리나 레드-블랙 트리처럼 삽입할 때마다 회전으로 높이를 O(log n)으로 유지하는 균형 이진 탐색 트리인 이유입니다. C++의 std::map, Java의 TreeMap이 레드-블랙 트리입니다. Python 표준 라이브러리에는 균형 BST가 없어서, 정렬 상태를 유지해야 할 때는 bisect 모듈로 정렬된 리스트를 관리하거나 서드파티 sortedcontainers를 씁니다.
반복문 구현:
def insert_bst_iterative(root, val):
# 빈 트리면 새 노드가 루트
if not root:
return TreeNode(val)
current = root
while True:
if val < current.val:
# 왼쪽으로 이동
if current.left is None:
# 빈 자리 발견 → 삽입
current.left = TreeNode(val)
break
current = current.left
else:
# 오른쪽으로 이동
if current.right is None:
# 빈 자리 발견 → 삽입
current.right = TreeNode(val)
break
current = current.right
return rootBST 검색
BST의 정렬 속성을 활용하여 효율적으로 검색합니다:
def search_bst(root, val):
# 기저 조건 1: 노드가 없으면 찾지 못함
if not root:
return None
# 기저 조건 2: 찾았음!
if root.val == val:
return root
# BST 규칙 활용: 왼쪽 < 부모 < 오른쪽
if val < root.val:
# val이 현재 노드보다 작으면 왼쪽 서브트리에만 있을 수 있음
# 오른쪽은 확인할 필요 없음 (모두 현재 노드보다 큼)
return search_bst(root.left, val)
else:
# val이 현재 노드보다 크면 오른쪽 서브트리에만 있을 수 있음
return search_bst(root.right, val)
# 트리 구조:
# 5
# / \
# 3 7
# / \ / \
# 2 4 6 8
# 검색 과정 (val=6 찾기):
# 1. root(5): 6 > 5 → 오른쪽으로 (왼쪽은 무시)
# 2. node(7): 6 < 7 → 왼쪽으로 (오른쪽은 무시)
# 3. node(6): 6 == 6 → 찾음!
#
# 총 3번 비교 (트리 높이만큼)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때 (매번 절반씩 제거)
# - 최악: O(n) - 한쪽으로 치우친 트리일 때
# 예: 1→2→3→4→5 (연결 리스트와 동일)
# 일반 배열 검색과 비교:
# 배열 (정렬 안 됨): O(n) - 모든 요소 확인 필요
# 배열 (정렬됨): O(log n) - 이진 탐색 가능
# BST: 균형이 유지될 때 O(log n) - 삽입/삭제도 O(log n)
# (정렬 배열은 삽입/삭제에 원소 이동이 필요해 O(n))정렬된 배열도 이진 탐색으로 O(log n) 검색이 되는데 BST를 쓰는 이유는 삽입과 삭제 때문입니다. 정렬된 배열에 값을 넣으려면 그 뒤의 원소를 모두 한 칸씩 밀어야 해서 O(n)이 들지만, 균형 BST는 포인터 몇 개만 바꾸면 됩니다. 반대로 데이터가 한 번 만들어진 뒤 바뀌지 않는다면 정렬 배열 + 이진 탐색이 메모리도 적게 쓰고 캐시 효율도 좋아 더 빠릅니다. 검색만 필요하고 순서가 필요 없다면 해시 테이블의 평균 O(1)이 가장 빠르므로, “정렬 순서가 필요한가, 데이터가 자주 바뀌는가”가 선택 기준입니다. 반복문 구현:
def search_bst_iterative(root, val):
current = root
while current:
if current.val == val:
# 찾았음!
return current
elif val < current.val:
# 왼쪽으로 이동
current = current.left
else:
# 오른쪽으로 이동
current = current.right
# 찾지 못함
return None
# 반복문이 재귀보다 메모리 효율적
# (함수 호출 스택 오버헤드 없음)BST의 장점:
# 정렬된 데이터 유지
# 중위 순회 시 자동으로 오름차순
def get_sorted(root):
return inorder(root) # O(n)
# 최소/최대값 찾기
def find_min(root):
# 가장 왼쪽 노드가 최소값
while root.left:
root = root.left
return root.val
def find_max(root):
# 가장 오른쪽 노드가 최대값
while root.right:
root = root.right
return root.valfind_min과 find_max는 빈 트리(root가 None)를 넘기면 AttributeError: 'NoneType' object has no attribute 'left'가 나므로 호출 전에 확인해야 합니다.
이 글에서 다루지 않은 BST 삭제는 세 경우로 나뉩니다. 자식이 없으면 그냥 지우고, 자식이 하나면 그 자식을 부모 자리에 올립니다. 자식이 둘이면 오른쪽 서브트리의 최소값(중위 후속자)을 찾아 현재 노드의 값을 그것으로 바꾼 뒤, 오른쪽 서브트리에서 그 후속자를 지웁니다. 후속자는 왼쪽 자식이 없으므로 앞의 두 경우 중 하나로 처리됩니다. 위 find_min이 바로 이 후속자를 찾는 데 쓰입니다.
실전 문제
문제 1: 트리 높이
def max_depth(root):
"""
트리의 최대 깊이
"""
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth(root)) # 3“왼쪽 서브트리의 답과 오른쪽 서브트리의 답을 구해서 합친다”는 트리 재귀의 전형입니다. 함수가 “이 노드를 루트로 하는 서브트리의 깊이”를 돌려준다고 믿고(재귀의 신뢰), 현재 노드에서는 둘 중 큰 값에 자기 자신 1을 더하기만 합니다. 모든 노드를 한 번씩 방문하므로 시간은 O(n), 재귀 스택은 트리 높이만큼 O(h)입니다.
같은 패턴을 조금 바꾸면 지름(두 노드 사이 가장 긴 경로, LeetCode 543)도 풉니다. 각 노드에서 left_depth + right_depth가 그 노드를 지나는 가장 긴 경로이므로, 깊이를 계산하는 김에 이 값의 최댓값을 바깥 변수에 기록하면 됩니다. 반환값(깊이)과 기록하는 값(지름)이 다르다는 점이 헷갈리는 부분이라, 처음 풀 때 지름을 반환값으로 만들려다 막히는 경우가 많습니다.
문제 2: 대칭 트리
def is_symmetric(root):
"""
트리가 좌우 대칭인지 확인
"""
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right) if root else True
# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)
print(is_symmetric(root)) # True대칭 여부는 한 서브트리만 보고는 판단할 수 없어서, 두 노드를 동시에 받는 보조 함수 is_mirror를 만들었습니다. 거울처럼 비추려면 왼쪽의 바깥쪽(left.left)과 오른쪽의 바깥쪽(right.right), 왼쪽의 안쪽(left.right)과 오른쪽의 안쪽(right.left)을 짝지어야 합니다. left.left와 right.left를 비교하는 실수를 하면 “두 서브트리가 같은 모양인가”를 검사하는 전혀 다른 함수가 됩니다.
기저 조건의 순서도 중요합니다. 둘 다 None이면 대칭, 하나만 None이면 비대칭을 먼저 걸러야 그 뒤의 left.val에서 None에 접근하는 에러가 나지 않습니다. 값만 같고 한쪽에만 자식이 있는 경우가 이 두 번째 조건에서 걸러집니다.
문제 3: 최소 공통 조상 (LCA)
def lowest_common_ancestor(root, p, q):
"""
두 노드의 최소 공통 조상 (BST)
"""
if not root:
return None
# 둘 다 왼쪽
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor(root.left, p, q)
# 둘 다 오른쪽
if p.val > root.val and q.val > root.val:
return lowest_common_ancestor(root.right, p, q)
# 갈라지는 지점 = LCA
return root이 풀이는 BST라는 전제를 이용합니다. 두 값이 모두 현재 노드보다 작으면 둘 다 왼쪽 서브트리에 있으므로 공통 조상도 그쪽에 있고, 둘 다 크면 오른쪽에 있습니다. 한쪽은 작고 한쪽은 크거나, 둘 중 하나가 현재 노드 자신이면 여기서 두 경로가 갈라지므로 현재 노드가 가장 낮은 공통 조상입니다. 한 경로만 따라 내려가므로 O(h)입니다.
일반 이진 트리(LeetCode 236)에는 이 방법을 쓸 수 없습니다. 값의 크기로 방향을 정할 수 없기 때문입니다. 그때는 후위 순회로 “이 서브트리에 p나 q가 있으면 그 노드를 반환”하게 만들고, 왼쪽과 오른쪽에서 모두 무언가가 돌아온 첫 노드를 답으로 삼습니다. 또 이 코드는 p와 q가 트리에 반드시 존재한다고 가정하므로, 존재하지 않을 수 있는 입력이라면 먼저 검색으로 확인해야 합니다. 트리가 고정되어 있고 LCA 질의가 수만 번 들어오는 문제(백준 11438 등)라면 매번 내려가는 대신 희소 배열로 2^k번째 조상을 미리 계산해 두는 이진 리프팅 기법으로 질의당 O(log n)에 답합니다.
트리 문제에서 순회 방법을 고르는 기준
순회 방법을 고르는 기준은 “정보가 어느 방향으로 흐르는가”입니다. 루트에서 내려가며 값을 전달해야 하면(현재까지의 경로 합, 허용 범위, 깊이) 전위 순회에 매개변수를 추가하고, 자식의 결과를 모아 올라와야 하면(높이, 크기, 서브트리 합) 후위 순회로 반환값을 씁니다. 루트에서 가까운 순서가 중요하면(최소 깊이, 레벨별 처리) 레벨 순회를 씁니다. 예를 들어 “루트에서 리프까지 가는 가장 짧은 경로”를 DFS로 찾으면 트리 전체를 봐야 하지만, BFS는 처음 만나는 리프에서 멈출 수 있습니다.
제가 트리 문제를 풀 때 막히면 가장 먼저 하는 일은 함수가 무엇을 반환하는지 한 문장으로 적는 것입니다. “이 함수는 node를 루트로 하는 서브트리의 높이를 반환한다”처럼 정의가 명확하면 재귀 호출 결과를 믿고 조합하는 코드가 거의 저절로 나옵니다. 반대로 반환값의 의미가 흐릿하면 기저 조건에서 0을 줄지 -1을 줄지, None일 때 무엇을 돌려줄지에서 계속 헤매게 됩니다.
추천 문제와 재귀 깊이 함정
트리 문제는 대부분 “현재 노드에서 무엇을 계산하고, 자식 쪽 결과를 어떻게 합칠지”만 정하면 재귀로 풀립니다. 그런데 Python으로 백준 문제를 풀 때 자주 걸리는 함정이 재귀 깊이입니다. Python의 기본 재귀 한도는 1000이라서, 노드가 최대 10만 개까지 주어지는 11725번처럼 트리가 한쪽으로 길게 늘어질 수 있는 입력에서는 RecursionError가 납니다. sys.setrecursionlimit으로 한도를 올리거나, 부모 찾기처럼 순서가 중요하지 않은 탐색은 BFS나 명시적 스택으로 바꾸는 편이 안전합니다.
백준:
프로그래머스:
LeetCode:
자주 묻는 질문 (FAQ)
Q. BST를 중위 순회하면 왜 정렬된 순서가 나오나요?
A. BST는 모든 노드에서 왼쪽 서브트리 값은 작고 오른쪽 서브트리 값은 크다는 규칙을 지킵니다. 중위 순회는 왼쪽 → 부모 → 오른쪽 순서로 방문하므로, 이 규칙을 재귀적으로 따라가면 자연히 작은 값부터 큰 값 순으로 출력됩니다. 그래서 중위 순회 결과가 오름차순인지 확인하는 방식으로 어떤 트리가 올바른 BST인지 검증하는 문제도 풀 수 있습니다.