개념
각 노드가 최대 2개의 자식을 가지는 트리 구조
계층적 데이터를 표현하는 비선형 자료구조
기본 용어
1 ← root (루트)
/ \
2 3 ← level 1
/ \ \
4 5 6 ← level 2 (leaf nodes)
- 루트(Root): 최상위 노드
- 부모(Parent): 상위 노드
- 자식(Child): 하위 노드
- 리프(Leaf): 자식이 없는 노드
- 레벨(Level): 루트로부터의 깊이
- 높이(Height): 루트부터 가장 깊은 노드까지의 거리
트리의 종류
1. 정 이진 트리 (Full Binary Tree)
모든 노드가 0개 또는 2개의 자식을 가짐
1
/ \
2 3
/ \
4 5
2. 완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외하고 모든 레벨이 완전히 채워짐
1
/ \
2 3
/ \ /
4 5 6
3. 포화 이진 트리 (Perfect Binary Tree)
모든 리프 노드가 같은 레벨에 있음
1
/ \
2 3
/ \ / \
4 5 6 7
4. 편향 트리 (Skewed Tree)
한쪽으로만 치우친 트리
1 1
/ \
2 2
\ \
3 3
Python 구현
1. 노드 클래스
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right2. 이진 트리 생성
# 수동으로 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 1
# / \
# 2 3
# / \
# 4 5트리 순회 (Tree Traversal)
1. 전위 순회 (Preorder: Root → Left → Right)
def preorder(root):
if not root:
return []
result = []
result.append(root.val)
result.extend(preorder(root.left))
result.extend(preorder(root.right))
return result
# 반복문 버전 (스택 사용)
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 오른쪽 먼저 push (나중에 처리)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 테스트: [1, 2, 4, 5, 3]활용: 트리 복사, 수식 트리의 전위 표기법
2. 중위 순회 (Inorder: Left → Root → Right)
def inorder(root):
if not root:
return []
result = []
result.extend(inorder(root.left))
result.append(root.val)
result.extend(inorder(root.right))
return result
# 반복문 버전
def inorder_iterative(root):
result = []
stack = []
current = root
while current or stack:
# 왼쪽 끝까지 이동
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
# 테스트: [4, 2, 5, 1, 3]활용: BST를 오름차순으로 출력
3. 후위 순회 (Postorder: Left → Right → Root)
def postorder(root):
if not root:
return []
result = []
result.extend(postorder(root.left))
result.extend(postorder(root.right))
result.append(root.val)
return result
# 반복문 버전
def postorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # 역순
# 테스트: [4, 5, 2, 3, 1]활용: 트리 삭제, 수식 트리의 후위 표기법
4. 레벨 순회 (Level Order: BFS)
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# 테스트: [[1], [2, 3], [4, 5]]활용: 레벨별 처리, 최단 경로
자주 나오는 문제 유형
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
# 테스트
# 1
# / \
# 2 3
# / \
# 4 5
# 결과: 3
# 시간복잡도: O(n)
# 공간복잡도: O(h) - h: 높이핵심: 재귀로 왼쪽/오른쪽 깊이 계산 후 최댓값 + 1
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
# 테스트
# 1
# / \
# 2 2
# / \ / \
# 3 4 4 3
# 결과: True
# 시간복잡도: O(n)핵심: 왼쪽 서브트리와 오른쪽 서브트리가 거울상인지 확인
3. 경로의 합
문제: 루트부터 리프까지 경로의 합이 target인지 확인
def has_path_sum(root, target_sum):
if not root:
return False
# 리프 노드 도달
if not root.left and not root.right:
return root.val == target_sum
# 자식 노드로 재귀
remaining = target_sum - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
# 테스트
# 5
# / \
# 4 8
# / / \
# 11 13 4
# / \ \
# 7 2 1
# has_path_sum(root, 22) → True (5→4→11→2)
# 시간복잡도: O(n)핵심: 리프 노드에서 합 비교, 재귀로 남은 합 전달
4. 트리의 지름
문제: 트리에서 가장 긴 경로의 길이
def diameter_of_tree(root):
diameter = 0
def depth(node):
nonlocal diameter
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
# 현재 노드를 거치는 경로 길이
diameter = max(diameter, left + right)
return max(left, right) + 1
depth(root)
return diameter
# 테스트
# 1
# / \
# 2 3
# / \
# 4 5
# 결과: 3 (4→2→1→3 또는 5→2→1→3)
# 시간복잡도: O(n)핵심: 각 노드에서 좌우 깊이의 합이 지름 후보
5. 최소 공통 조상 (LCA)
문제: 두 노드의 최소 공통 조상 찾기
def lowest_common_ancestor(root, p, q):
# Base Case
if not root or root == p or root == q:
return root
# 왼쪽과 오른쪽 서브트리에서 탐색
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# 양쪽 모두에서 발견 → 현재 노드가 LCA
if left and right:
return root
# 한쪽에서만 발견 → 그쪽 결과 반환
return left if left else right
# 테스트
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) → 3
# LCA(5, 4) → 5
# 시간복잡도: O(n)핵심: 양쪽 서브트리에서 모두 발견되는 첫 노드
6. 트리 평탄화 (Flatten to Linked List)
문제: 이진 트리를 연결 리스트로 평탄화
def flatten(root):
if not root:
return
# 후위 순회로 오른쪽부터 처리
flatten(root.right)
flatten(root.left)
# 왼쪽을 오른쪽으로 이동
right_subtree = root.right
root.right = root.left
root.left = None
# 원래 오른쪽을 맨 끝에 연결
current = root
while current.right:
current = current.right
current.right = right_subtree
# 테스트
# 1 1
# / \ \
# 2 5 → 2
# / \ \ \
# 3 4 6 3
# \
# 4
# \
# 5
# \
# 6
# 시간복잡도: O(n)핵심: 왼쪽 서브트리를 오른쪽으로 옮기고 원래 오른쪽을 끝에 연결
추천 연습 문제
기초
중급
- LeetCode 101 - Symmetric Tree
- LeetCode 112 - Path Sum
- LeetCode 543 - Diameter of Binary Tree
- 백준 1167번 - 트리의 지름
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 전위 순회 | Root → Left → Right |
| 중위 순회 | Left → Root → Right |
| 후위 순회 | Left → Right → Root |
| 레벨 순회 | BFS로 레벨별 탐색 |
트리 순회 선택 가이드
전위 순회 사용 시기
- 트리 복사
- 수식 트리의 전위 표기법
- 트리 구조를 그대로 출력
중위 순회 사용 시기
- BST를 정렬된 순서로 출력
- 수식 트리의 중위 표기법
후위 순회 사용 시기
- 트리 삭제 (자식부터 삭제)
- 디렉토리 크기 계산
- 수식 트리 계산
레벨 순회 사용 시기
- 레벨별 처리
- 최단 경로 문제
- 트리를 레벨별로 출력
트리 문제 해결 패턴
1. 재귀 템플릿
def solve(root):
# Base Case
if not root:
return base_value
# 왼쪽, 오른쪽 서브트리 처리
left_result = solve(root.left)
right_result = solve(root.right)
# 현재 노드 처리
return combine(root.val, left_result, right_result)2. 레벨별 처리 템플릿
def level_process(root):
if not root:
return
queue = deque([root])
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# 노드 처리
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)3. 두 트리 비교 템플릿
def compare(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
return (root1.val == root2.val and
compare(root1.left, root2.left) and
compare(root1.right, root2.right))시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 순회 | O(n) |
| 탐색 | O(n) - 일반 트리, O(log n) - 균형 트리 |
| 삽입 | O(n) - 일반 트리, O(log n) - 균형 트리 |
| 삭제 | O(n) - 일반 트리, O(log n) - 균형 트리 |