Name	Name	Last commit message	Last commit date
parent directory ..
README.md	README.md

Tree (트리)

1. 개념 및 정의

1.1 트리란?

트리(Tree)는 계층적 관계를 표현하는 비선형 자료구조입니다.

부모 노드와 자식 노드의 관계로 구성
하나의 루트에서 시작하여 아래로 확장
사이클(순환)이 없는 연결 그래프

코딩테스트에서는 이진트리가 무조건 출제! 다른 트리가 합쳐지면 오래 걸림 → 빠른 포기 권장

1.2 일상 속 트리의 예

예시	설명
가계도	조상-자손 관계
회사 조직도	상사-부하 관계
파일 시스템	폴더-파일 계층 구조
HTML DOM	태그의 부모-자식 관계
토너먼트 대진표	경기 순서와 결과

1.3 트리 vs 그래프

특성	트리 (Tree)	그래프 (Graph)
사이클	없음	있을 수 있음
루트	있음 (하나)	없음
방향성	있음 (위→아래)	있거나 없음
부모-자식	명확함	없음
노드 간 경로	유일함	여러 개 가능

2. 트리 용어

2.1 용어 도해

                    ┌───────────┐
                    │     A     │ ← 루트 노드 (Root)
                    │  (깊이 0) │   레벨 0
                    └─────┬─────┘
                          │
            ┌─────────────┼─────────────┐
            │             │             │
      ┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
      │     B     │ │     C     │ │     D     │ ← 내부 노드
      │  (깊이 1) │ │  (깊이 1) │ │  (깊이 1) │   레벨 1
      └─────┬─────┘ └───────────┘ └─────┬─────┘
            │                           │
      ┌─────┴─────┐               ┌─────┴─────┐
      │           │               │           │
┌─────▼─────┐┌────▼────┐   ┌─────▼─────┐┌────▼────┐
│     E     ││    F    │   │     G     ││    H    │
│  (깊이 2) ││(깊이 2) │   │  (깊이 2) ││(깊이 2) │ ← 단말 노드
└───────────┘└─────────┘   └───────────┘└─────────┘   (Leaf)
                                                      레벨 2

              트리의 높이 (Height) = 2

2.2 용어 정리표

용어	영문	설명	예시 (위 그림 기준)
루트 노드	Root Node	트리의 최상단 노드 (부모가 없음)	A
단말 노드	Leaf Node / Terminal Node	자식이 없는 최하단 노드	E, F, C, G, H
내부 노드	Internal Node	루트도 단말도 아닌 중간 노드	B, D
부모 노드	Parent Node	자식이 있는 노드	A는 B,C,D의 부모
자식 노드	Child Node	부모의 하위 노드	B,C,D는 A의 자식
형제 노드	Sibling Node	같은 부모를 가진 노드들	B, C, D는 형제
조상 노드	Ancestor Node	루트까지의 경로에 있는 노드들	E의 조상: B, A
자손 노드	Descendant Node	해당 노드 아래의 모든 노드	A의 자손: B,C,D,E,F,G,H
차수	Degree	노드가 가진 자식 수	A의 차수: 3, B의 차수: 2
깊이	Depth	루트부터의 거리 (간선 수)	E의 깊이: 2
레벨	Level	같은 깊이의 노드 집합	레벨 1: B, C, D
높이	Height	트리의 최대 깊이	높이: 2
서브트리	Subtree	트리의 부분 집합 (그 자체도 트리)	B를 루트로 하는 서브트리

2.3 차수 (Degree)

차수 = 해당 노드가 가지고 있는 자식 노드의 수

예시:
- A의 차수: 3 (B, C, D)
- B의 차수: 2 (E, F)
- C의 차수: 0 (단말 노드)
- 트리의 차수: 노드 중 최대 차수 = 3

이진 트리: 모든 노드의 차수가 2 이하인 트리

3. 트리의 특징

3.1 5가지 핵심 특징

┌─────────────────────────────────────────────────────────────────┐
│  트리의 5가지 핵심 특징                                         │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. 부모-자식 관계                                              │
│     → 트리는 부모 노드와 자식 노드의 관계로 표현된다           │
│                                                                 │
│  2. 루트 노드                                                   │
│     → 트리의 최상단 노드를 루트 노드(Root Node)라 한다         │
│                                                                 │
│  3. 단말 노드                                                   │
│     → 트리의 최하단 노드(자식이 없는 노드)를 단말 노드라 한다  │
│                                                                 │
│  4. 서브트리                                                    │
│     → 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브트리라 함│
│                                                                 │
│  5. 계층 구조                                                   │
│     → 파일 시스템과 같이 계층 구조를 이루고,                   │
│       정렬된 데이터를 다루기에 적합하다                        │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

3.2 트리의 성질

노드가 N개인 트리는 N-1개의 간선을 가진다
루트에서 특정 노드까지의 경로는 유일하다
임의의 두 노드 사이의 경로도 유일하다
트리는 사이클(순환)이 없는 연결 그래프이다

4. 트리의 종류

4.1 종류 비교표

종류	설명	특징
일반 트리	차수 제한 없음	자식 수 제한 없음
이진 트리	차수가 최대 2	왼쪽, 오른쪽 자식만
이진 탐색 트리	정렬된 이진 트리	왼쪽 < 부모 < 오른쪽
완전 이진 트리	왼쪽부터 채워진 이진 트리	힙 구현에 사용
포화 이진 트리	모든 레벨이 꽉 찬 이진 트리	노드 수 = 2^h - 1
균형 이진 트리	좌우 높이 차이 <= 1	AVL, 레드-블랙 트리

4.2 이진 트리 종류 시각화

완전 이진 트리 (Complete Binary Tree)
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워짐
- 마지막 레벨은 왼쪽부터 채워짐

         1              ✓ 완전 이진 트리
       /   \
      2     3
     / \   /
    4   5 6

포화 이진 트리 (Full/Perfect Binary Tree)
- 모든 레벨이 완전히 채워짐
- 노드 수 = 2^(h+1) - 1 (h: 높이)

         1              ✓ 포화 이진 트리
       /   \
      2     3
     / \   / \
    4   5 6   7

편향 이진 트리 (Skewed Binary Tree)
- 한쪽 방향으로만 노드가 있음
- 최악의 경우 (사실상 연결 리스트)

    1                   1
     \                 /
      2               2
       \             /
        3           3
         \         /
          4       4
  (우편향)        (좌편향)

5. 이진 트리

5.1 이진 트리란?

모든 노드의 차수가 2 이하인 트리
각 노드는 최대 2개의 자식을 가짐 (왼쪽, 오른쪽)
왼쪽 자식과 오른쪽 자식은 구분됨

5.2 이진 트리의 속성

속성	공식	설명
최대 노드 수	2^(h+1) - 1	높이 h인 이진 트리의 최대 노드 수
레벨 l의 최대 노드 수	2^l	레벨 l에 있을 수 있는 최대 노드 수
리프 노드 수	n0 = n2 + 1	차수 0인 노드 = 차수 2인 노드 + 1
최소 높이	log2(n+1) - 1	n개 노드의 이진 트리 최소 높이

5.3 배열로 이진 트리 표현

완전 이진 트리는 배열로 효율적으로 표현 가능

         1                인덱스 관계:
       /   \              - 부모: (i-1) // 2
      2     3             - 왼쪽 자식: 2*i + 1
     / \   / \            - 오른쪽 자식: 2*i + 2
    4   5 6   7

인덱스: 0  1  2  3  4  5  6
배열:  [1, 2, 3, 4, 5, 6, 7]

# 배열 인덱스로 이진 트리 관계 표현
def parent(i):
    return (i - 1) // 2

def left_child(i):
    return 2 * i + 1

def right_child(i):
    return 2 * i + 2

# 예시
tree = [1, 2, 3, 4, 5, 6, 7]

# 인덱스 1의 부모
print(tree[parent(1)])  # tree[0] = 1

# 인덱스 1의 왼쪽 자식
print(tree[left_child(1)])  # tree[3] = 4

# 인덱스 1의 오른쪽 자식
print(tree[right_child(1)])  # tree[4] = 5

6. 이진 탐색 트리 (BST)

6.1 이진 탐색 트리란?

이진 탐색 트리(Binary Search Tree, BST)는 정렬된 이진 트리입니다.

핵심 규칙: 왼쪽 자식 < 부모 < 오른쪽 자식

6.2 BST의 특성

이진 탐색 트리 예시:

              8
            /   \
           3     10
          / \      \
         1   6     14
            / \    /
           4   7  13

특성:
1. 왼쪽 서브트리의 모든 값 < 루트 값
2. 오른쪽 서브트리의 모든 값 > 루트 값
3. 왼쪽, 오른쪽 서브트리도 각각 BST

예시 검증:
- 노드 8: 왼쪽(3,1,6,4,7) 모두 < 8 ✓
          오른쪽(10,14,13) 모두 > 8 ✓
- 노드 3: 왼쪽(1) < 3 ✓
          오른쪽(6,4,7) > 3 ✓

6.3 BST vs 일반 이진 트리

특성	이진 트리	이진 탐색 트리
차수	최대 2	최대 2
정렬	없음	왼쪽 < 부모 < 오른쪽
탐색	O(n)	O(log n) 평균
삽입	어디든 가능	규칙에 따라 위치 결정
중위 순회	의미 없음	정렬된 순서 출력

6.4 BST 주요 연산

6.4.1 탐색 (Search)

def search_bst(node, target):
    """
    BST에서 값 탐색
    - target이 현재 노드보다 작으면 왼쪽으로
    - target이 현재 노드보다 크면 오른쪽으로
    """
    if node is None:
        return None  # 못 찾음

    if target == node.val:
        return node  # 찾음
    elif target < node.val:
        return search_bst(node.left, target)  # 왼쪽 탐색
    else:
        return search_bst(node.right, target)  # 오른쪽 탐색

6.4.2 삽입 (Insert)

def insert_bst(node, val):
    """
    BST에 값 삽입
    - 탐색과 같은 방식으로 위치를 찾아서 삽입
    """
    if node is None:
        return TreeNode(val)  # 새 노드 생성

    if val < node.val:
        node.left = insert_bst(node.left, val)
    else:
        node.right = insert_bst(node.right, val)

    return node

6.4.3 삭제 (Delete)

def delete_bst(node, val):
    """
    BST에서 값 삭제
    - 경우 1: 리프 노드 → 그냥 삭제
    - 경우 2: 자식 1개 → 자식으로 대체
    - 경우 3: 자식 2개 → 오른쪽 서브트리의 최소값으로 대체
    """
    if node is None:
        return None

    if val < node.val:
        node.left = delete_bst(node.left, val)
    elif val > node.val:
        node.right = delete_bst(node.right, val)
    else:
        # 찾음 - 삭제 수행
        if node.left is None:
            return node.right  # 경우 1, 2
        elif node.right is None:
            return node.left   # 경우 2

        # 경우 3: 오른쪽 서브트리의 최소값 찾기
        min_node = find_min(node.right)
        node.val = min_node.val
        node.right = delete_bst(node.right, min_node.val)

    return node

def find_min(node):
    """가장 왼쪽 노드 (최소값) 찾기"""
    while node.left:
        node = node.left
    return node

7. 트리 순회

7.1 순회 방식 개요

트리의 모든 노드를 방문하는 방법은 크게 4가지가 있습니다.

순회 방식	영문	순서	기억법
전위 순회	Preorder	루트 → 왼쪽 → 오른쪽	VLR (Visit first)
중위 순회	Inorder	왼쪽 → 루트 → 오른쪽	LVR (Visit middle)
후위 순회	Postorder	왼쪽 → 오른쪽 → 루트	LRV (Visit last)
레벨 순회	Level-order	레벨별 왼쪽→오른쪽	BFS 방식

7.2 순회 예시

예시 트리:
         1
       /   \
      2     3
     / \   / \
    4   5 6   7

전위 순회 (Preorder): 1 → 2 → 4 → 5 → 3 → 6 → 7
- 루트를 먼저 방문
- "부모 → 왼쪽 자식 → 오른쪽 자식"

중위 순회 (Inorder): 4 → 2 → 5 → 1 → 6 → 3 → 7
- 왼쪽 서브트리 먼저, 루트, 오른쪽 서브트리
- BST에서는 정렬된 순서!

후위 순회 (Postorder): 4 → 5 → 2 → 6 → 7 → 3 → 1
- 자식들을 먼저 방문
- 트리 삭제, 폴더 크기 계산에 유용

레벨 순회 (Level-order): 1 → 2 → 3 → 4 → 5 → 6 → 7
- 위에서 아래로, 왼쪽에서 오른쪽
- BFS 방식

7.3 순회 구현 (재귀)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node, result=None):
    """전위 순회: 루트 → 왼쪽 → 오른쪽"""
    if result is None:
        result = []

    if node:
        result.append(node.val)      # 1. 루트 방문
        preorder(node.left, result)  # 2. 왼쪽 서브트리
        preorder(node.right, result) # 3. 오른쪽 서브트리

    return result

def inorder(node, result=None):
    """중위 순회: 왼쪽 → 루트 → 오른쪽"""
    if result is None:
        result = []

    if node:
        inorder(node.left, result)   # 1. 왼쪽 서브트리
        result.append(node.val)      # 2. 루트 방문
        inorder(node.right, result)  # 3. 오른쪽 서브트리

    return result

def postorder(node, result=None):
    """후위 순회: 왼쪽 → 오른쪽 → 루트"""
    if result is None:
        result = []

    if node:
        postorder(node.left, result)  # 1. 왼쪽 서브트리
        postorder(node.right, result) # 2. 오른쪽 서브트리
        result.append(node.val)       # 3. 루트 방문

    return result

7.4 순회 구현 (반복 - 스택 사용)

def preorder_iterative(root):
    """전위 순회 - 반복 (스택 사용)"""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # 오른쪽 먼저 push (왼쪽이 먼저 pop되도록)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

def inorder_iterative(root):
    """중위 순회 - 반복 (스택 사용)"""
    result = []
    stack = []
    current = root

    while stack or current:
        # 왼쪽 끝까지 이동
        while current:
            stack.append(current)
            current = current.left

        # 방문
        current = stack.pop()
        result.append(current.val)

        # 오른쪽으로 이동
        current = current.right

    return result

def postorder_iterative(root):
    """후위 순회 - 반복 (스택 2개 사용)"""
    if not root:
        return []

    result = []
    stack1 = [root]
    stack2 = []

    while stack1:
        node = stack1.pop()
        stack2.append(node)

        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)

    while stack2:
        result.append(stack2.pop().val)

    return result

7.5 레벨 순회 (BFS)

from collections import deque

def level_order(root):
    """레벨 순회 - BFS (큐 사용)"""
    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

def level_order_by_level(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, 6, 7]]

7.6 순회 활용

순회 방식	활용 예시
전위 순회	트리 복사, 트리 출력, 표현식의 전위 표기법
중위 순회	BST의 정렬된 순서 출력, 표현식의 중위 표기법
후위 순회	트리 삭제, 폴더 크기 계산, 표현식의 후위 표기법
레벨 순회	레벨별 처리, 최단 경로, 트리 시각화

8. 구현 코드

8.1 노드 클래스

class TreeNode:
    """이진 트리 노드"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.val)

8.2 이진 탐색 트리 클래스

class BinarySearchTree:
    """이진 탐색 트리"""

    def __init__(self):
        self.root = None

    def insert(self, val):
        """값 삽입"""
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)

    def _insert_recursive(self, node, val):
        if val < node.val:
            if node.left:
                self._insert_recursive(node.left, val)
            else:
                node.left = TreeNode(val)
        else:
            if node.right:
                self._insert_recursive(node.right, val)
            else:
                node.right = TreeNode(val)

    def search(self, val):
        """값 검색"""
        return self._search_recursive(self.root, val)

    def _search_recursive(self, node, val):
        if not node:
            return None
        if val == node.val:
            return node
        elif val < node.val:
            return self._search_recursive(node.left, val)
        else:
            return self._search_recursive(node.right, val)

    def inorder(self):
        """중위 순회 (정렬된 순서)"""
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.val)
            self._inorder_recursive(node.right, result)

    def min_value(self):
        """최소값"""
        if not self.root:
            return None
        node = self.root
        while node.left:
            node = node.left
        return node.val

    def max_value(self):
        """최대값"""
        if not self.root:
            return None
        node = self.root
        while node.right:
            node = node.right
        return node.val

    def height(self):
        """트리 높이"""
        return self._height_recursive(self.root)

    def _height_recursive(self, node):
        if not node:
            return -1  # 빈 트리의 높이는 -1
        left_height = self._height_recursive(node.left)
        right_height = self._height_recursive(node.right)
        return max(left_height, right_height) + 1

# 사용 예시
bst = BinarySearchTree()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(val)

print(bst.inorder())     # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(bst.min_value())   # 1
print(bst.max_value())   # 14
print(bst.height())      # 3
print(bst.search(6))     # TreeNode(6)

8.3 리스트로 트리 구성 (코딩테스트용)

# 코딩테스트에서 자주 사용하는 트리 표현
# - 인접 리스트로 트리 표현
# - 부모-자식 관계를 딕셔너리나 리스트로 저장

def build_tree_from_edges(n, edges):
    """
    간선 리스트로부터 트리 구성

    Args:
        n: 노드 수
        edges: [(부모, 자식), ...] 형태의 간선 리스트

    Returns:
        tree: 인접 리스트
    """
    tree = [[] for _ in range(n + 1)]
    for parent, child in edges:
        tree[parent].append(child)
    return tree

# 예시
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]
tree = build_tree_from_edges(7, edges)
print(tree)  # [[], [2, 3], [4, 5], [6, 7], [], [], [], []]

9. 실전 문제

9.1 문제 1: 트리의 높이 구하기

def tree_height(root):
    """트리의 높이 계산"""
    if not root:
        return -1

    left_height = tree_height(root.left)
    right_height = tree_height(root.right)

    return max(left_height, right_height) + 1

9.2 문제 2: 트리의 노드 개수

def count_nodes(root):
    """트리의 노드 개수 계산"""
    if not root:
        return 0

    return 1 + count_nodes(root.left) + count_nodes(root.right)

9.3 문제 3: 이진 트리의 최대 깊이 (LeetCode 104)

def maxDepth(root):
    """
    이진 트리의 최대 깊이

    깊이 = 루트에서 가장 먼 리프까지의 노드 수
    """
    if not root:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return max(left_depth, right_depth) + 1

9.4 문제 4: 대칭 트리 (LeetCode 101)

def isSymmetric(root):
    """대칭 트리 확인"""
    if not root:
        return True

    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)

9.5 문제 5: BST 유효성 검사 (LeetCode 98)

def isValidBST(root):
    """이진 탐색 트리인지 확인"""
    def validate(node, min_val, max_val):
        if not node:
            return True

        if node.val <= min_val or node.val >= max_val:
            return False

        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))

9.6 문제 6: 가장 가까운 공통 조상 (LCA)

def lowestCommonAncestor(root, p, q):
    """
    두 노드의 가장 가까운 공통 조상 찾기
    """
    if not root or root == p or root == q:
        return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    if left and right:
        return root  # p와 q가 각각 좌우에 있음

    return left if left else right

10. 시간복잡도

10.1 이진 탐색 트리 연산

연산	평균	최악 (편향 트리)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

10.2 트리 순회

순회 방식	시간복잡도	공간복잡도 (재귀)
전위 순회	O(n)	O(h)
중위 순회	O(n)	O(h)
후위 순회	O(n)	O(h)
레벨 순회	O(n)	O(w)

n: 노드 수

h: 트리 높이

w: 트리의 최대 너비

10.3 균형 트리 vs 편향 트리

균형 트리 (Balanced Tree)
- 높이: O(log n)
- 탐색/삽입/삭제: O(log n)

         4
       /   \
      2     6
     / \   / \
    1   3 5   7

편향 트리 (Skewed Tree)
- 높이: O(n)
- 탐색/삽입/삭제: O(n)

    1
     \
      2
       \
        3
         \
          4

참고 자료

트리 문제 접근법

1. 재귀적 사고
   - 트리 문제의 대부분은 재귀로 해결
   - "이 노드에서 무엇을 해야 하는가?"를 먼저 생각

2. 순회 방식 선택
   - 부모 먼저 처리 → 전위 순회
   - 정렬 순서 필요 → 중위 순회
   - 자식 먼저 처리 → 후위 순회
   - 레벨별 처리 → 레벨 순회 (BFS)

3. BST 특성 활용
   - 값 비교로 탐색 방향 결정
   - 중위 순회 = 정렬된 순서

자주 출제되는 트리 문제 유형

유형	예시
순회	전위/중위/후위 순회 결과
높이/깊이	트리 높이, 최대 깊이
BST	유효성 검사, 탐색, 삽입
LCA	공통 조상 찾기
대칭	대칭 트리, 미러 트리
경로	경로 합, 최장 경로

FilesExpand file tree

C_03_Tree

Directory actions

More options

Directory actions

More options

Latest commit

History

C_03_Tree

Folders and files

parent directory

README.md

Tree (트리)

목차

1. 개념 및 정의

1.1 트리란?

1.2 일상 속 트리의 예

1.3 트리 vs 그래프

2. 트리 용어

2.1 용어 도해

2.2 용어 정리표

2.3 차수 (Degree)

3. 트리의 특징

3.1 5가지 핵심 특징

3.2 트리의 성질

4. 트리의 종류

4.1 종류 비교표

4.2 이진 트리 종류 시각화

5. 이진 트리

5.1 이진 트리란?

5.2 이진 트리의 속성

5.3 배열로 이진 트리 표현

6. 이진 탐색 트리 (BST)

6.1 이진 탐색 트리란?

6.2 BST의 특성

6.3 BST vs 일반 이진 트리

6.4 BST 주요 연산

6.4.1 탐색 (Search)

6.4.2 삽입 (Insert)

6.4.3 삭제 (Delete)

7. 트리 순회

7.1 순회 방식 개요

7.2 순회 예시

7.3 순회 구현 (재귀)

7.4 순회 구현 (반복 - 스택 사용)

7.5 레벨 순회 (BFS)

7.6 순회 활용

8. 구현 코드

8.1 노드 클래스

8.2 이진 탐색 트리 클래스

8.3 리스트로 트리 구성 (코딩테스트용)

9. 실전 문제

9.1 문제 1: 트리의 높이 구하기

9.2 문제 2: 트리의 노드 개수

9.3 문제 3: 이진 트리의 최대 깊이 (LeetCode 104)

9.4 문제 4: 대칭 트리 (LeetCode 101)

9.5 문제 5: BST 유효성 검사 (LeetCode 98)

9.6 문제 6: 가장 가까운 공통 조상 (LCA)

10. 시간복잡도

10.1 이진 탐색 트리 연산

10.2 트리 순회

10.3 균형 트리 vs 편향 트리

참고 자료

트리 문제 접근법

자주 출제되는 트리 문제 유형