[2026] 트리 자료구조 | 이진 트리, BST, 순회 완벽 정리
![[2026] 트리 자료구조 | 이진 트리, BST, 순회 완벽 정리](/og/s/algorithm-series-04-tree.webp)
이 글의 핵심
트리 자료구조: 이진 트리, BST, 순회 트리 기본 개념·트리 순회.
🎯 이 글을 읽으면 (읽는 시간: 22분)
TL;DR: 계층 구조를 표현하는 트리 자료구조를 완벽하게 마스터합니다. 이진 트리, BST, 트리 순회(전위/중위/후위)를 이해하고, 파일 시스템부터 코딩 테스트까지 실전 활용 능력을 습득합니다. 이 글을 읽으면:
- ✅ 트리, 이진 트리, BST 개념 완벽 이해
- ✅ 전위/중위/후위/레벨 순회 패턴 마스터
- ✅ 트리 문제 해결 능력 (깊이, 경로, 균형) 습득 실무 활용:
- 🔥 파일 시스템, DOM 트리 구조
- 🔥 데이터베이스 인덱스 (B-Tree)
- 🔥 코딩 테스트 (LeetCode Tree 문제) 난이도: 중급 | 실습 문제: 10개 | Python + C++: 모두 포함
들어가며
”계층 구조의 완벽한 표현”
트리는 계층 구조를 표현하는 자료구조입니다. 파일 시스템, DOM, 조직도 등 모두 트리입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 트리 기본 개념
용어
아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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): 같은 깊이의 노드들Python 구현
아래는 값(val)과 왼쪽·오른쪽 자식 포인터를 갖는 노드를 정의하고, 루트에서 아래로 가지를 뻗어 연결하는 예입니다. 조직도나 가계도처럼 한 부모 아래에 자식이 달리는 구조를 코드로 만든 것입니다.
아래 코드는 python를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)2. 트리 순회
전위 순회 (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) 반복문 구현 (스택 사용): 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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에서는 오름차순!후위 순회 (Postorder)
왼쪽 → 오른쪽 → 부모:
def postorder(node):
if not node:
return []
return postorder(node.left) + postorder(node.right) + [node.val]
# 결과: [4, 5, 2, 3, 1]레벨 순회 (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]3. 이진 탐색 트리 (BST)
BST 규칙
왼쪽 < 부모 < 오른쪽: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
5
/ \
3 7
/ \ / \
2 4 6 8
중위 순회: [2, 3, 4, 5, 6, 7, 8] (정렬됨!)BST 삽입
BST의 규칙을 유지하며 새 값을 삽입합니다: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)반복문 구현: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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의 정렬 속성을 활용하여 효율적으로 검색합니다: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)으로 유지반복문 구현: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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의 장점: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 정렬된 데이터 유지
# 중위 순회 시 자동으로 오름차순
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.val4. 실전 문제
문제 1: 트리 높이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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문제 2: 대칭 트리
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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문제 3: 최소 공통 조상 (LCA)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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실전 팁
트리 문제 접근법
아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 1. 재귀 생각
# 대부분 트리 문제는 재귀로 풀림
# 2. Base Case 명확히
# if not root: return ...
# 3. 순회 방법 선택
# 전위: 부모 먼저 처리
# 중위: BST 정렬
# 후위: 자식 먼저 처리
# 레벨: 최단 경로정리
핵심 요약
- 트리: 계층 구조, 루트-자식 관계
- 순회: 전위, 중위, 후위, 레벨
- BST: 왼쪽 < 부모 < 오른쪽, O(log n) 검색
- 재귀: 대부분 재귀로 해결
추천 문제
백준:
- 1991번: 트리 순회
- 11725번: 트리의 부모 찾기 프로그래머스:
- 길 찾기 게임 LeetCode:
- 104. Maximum Depth
- 101. Symmetric Tree