Technical Interview Master Plan[10] - Trees DFS/BFS는 아는데 왜 트리 문제에서 자꾸 막힐까

문제 해결을 위한 트리 구조에 대해 알아보도록 합니다.

Apr 01, 2026

∙ Paid

Trees

트리는 노드(node) 로 이루어진 계층적(hierarchical) 자료구조이며, 각 노드는 하나 이상의 자식 노드에 연결된다. 트리의 각 노드는 자신이 저장하는 데이터(val)와 자식 노드들에 대한 참조를 포함한다. 가장 흔한 트리의 종류는 이진 트리(binary tree) 이며, 이 경우 각 노드는 최대 두 개의 자식, 즉 왼쪽 자식(left child) 과 오른쪽 자식(right child) 에 연결된다.

`TreeNode` Class 클래스

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

Terminology

Parent(부모) - 하나 이상의 자식을 가진 노드.
Child(자식) - 부모를 가진 노드.
Subtree(서브트리) - 어떤 노드와 그 자손(descendants)들로 이루어진 트리.
Path(경로) - 간선으로 연결된 노드들의 단일하고 연속적인 순서열.
Depth(깊이) - 루트로부터 특정 노드까지의 간선 수.

Attributes of a tree 트리의 속성

Root(루트) - 트리의 가장 위쪽 노드이며, 부모가 없는 유일한 노드.
Intermediate node(중간 노드) - 부모 노드가 있고 적어도 하나의 자식을 가진 노드.
Leaf(리프) - 자식이 없는 노드.
Edge(간선) - 두 노드를 연결하는 것. 트리는 보통 방향성 간선(directed edges) 을 가지며, 이는 간선이 부모에서 자식 방향으로만 향한다는 뜻이다.
Height(높이) - 루트에서 리프까지의 가장 긴 경로의 길이.

이후의 설명에서는 주로 이진 트리(binary trees) 에 초점을 맞춘다.

Tree Traversals - 트리 순회

깊이 우선 탐색 (DFS)

DFS는 루트에서 시작하여 한 갈래(branch)를 가능한 한 깊게 내려간 뒤, 다시 되돌아와(backtracking) 다른 갈래를 탐색하는 방식으로 트리의 모든 노드를 탐색하는 방법이다.

DFS는 보통 재귀적으로 구현되며, 아래 코드와 비슷한 구조를 따른다.

def dfs(node: TreeNode):
    if node is None:
        return

    process(node)      # 현재 노드를 처리한다.
    dfs(node.left)     # 왼쪽 서브트리를 순회한다.
    dfs(node.right)    # 오른쪽 서브트리를 순회한다.

위의 재귀 구현은 전위 순회(preorder traversal) 의 순서를 따른다. 자주 쓰이는 다른 DFS 순회 기법 두 가지는 중위 순회(inorder traversal) 와 후위 순회(postorder traversal) 이다. 차이는 다음과 같다.

Preorder traversal - 전위 순회

process(node)
dfs(node.left)
dfs(node.right)

Inorder traversal - 중위 순회

dfs(node.left)
process(node)
dfs(node.right)

Postorder traversal - 후위 순회

dfs(node.left)
dfs(node.right)
process(node)

DFS는 활용 범위가 매우 넓고, 트리 순회에서 가장 흔히 선택되는 방법이다.

전위 순회(preorder traversal) 는 가장 흔한 DFS 순회 방식이다. 또한 각 서브트리의 루트 노드를 그 자식들보다 먼저 처리해야 할 때 사용된다.
중위 순회(inorder traversal) 는 트리의 노드들을 왼쪽에서 오른쪽으로 처리하고 싶을 때 사용된다.
후위 순회(postorder traversal) 는 세 가지 중 가장 덜 자주 쓰이지만, 각 노드의 서브트리가 루트보다 먼저 처리되어야 할 때 중요하다.

이 장의 문제들은 DFS 사용 사례를 더 자세히 탐구하며, 이러한 순회 방식들을 언제 어떻게 적용하는지에 대한 실용적인 예시를 제공한다.

너비 우선 탐색 (BFS)

BFS는 트리의 노드들을 레벨 단위(level by level) 로 순회한다. 현재 레벨의 노드들을 먼저 처리한 뒤, 다음 깊이 레벨의 노드들로 이동한다.

BFS는 보통 큐(queue) 를 사용해 반복적으로 구현되며, 이유는 이 장의 문제들을 진행하면서 더 분명해질 것이다. BFS의 기본 구조는 아래 코드 조각에 잘 드러나 있다.

def bfs(root: TreeNode):
    if root is None:
        return

    queue = deque([root])

    while queue:
        node = queue.popleft()
        process(node)   
        # 현재 노드를 처리한다.

        if node.left:
            # 왼쪽 자식을 큐에 추가한다.
            queue.append(node.left)

        if node.right:
            # 오른쪽 자식을 큐에 추가한다.
            queue.append(node.right)

BFS는 보통 트리에서 특정 목적지까지의 최단 경로(shortest path) 를 찾거나, 트리를 레벨별로(level by level) 처리할 때 사용된다. 순회 중 각 노드가 어떤 레벨에 있는지를 아는 것이 중요할 때는 레벨 순회(level-order traversal) 라는 BFS의 변형을 사용하는데, 이는 이 장에서 자세히 다룬다.

Complexity breakdown 복잡도 분석

아래에서 n은 트리의 노드 수를, h는 트리의 높이를 의미한다.

DFS - 시간복잡도: O(n) / 공간복잡도: O(h)

DFS는 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n) 이다. 공간 복잡도는 재귀 호출 스택의 최대 깊이에 의해 결정되며, 이는 트리의 높이 h만큼 깊어질 수 있다. 최악의 경우 트리의 높이는 n이고, 높이가 최소화된 균형 트리의 경우 높이는 대략 log(n) 이다.

BFS - 시간복잡도: O(n) / 공간복잡도: O(n)

BFS는 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n) 이다. 공간 복잡도는 어느 시점이든 큐에 저장되는 최대 노드 수에 의해 결정된다. 최악의 경우 큐는 트리의 맨 아래 레벨 전체를 저장할 수 있으며, 이 레벨에는 대략 n/2 개의 노드가 있을 수 있다.

Real-world 실제 시나리오

파일 시스템(File systems)

많은 운영체제에서 파일 시스템은 계층적 트리 구조로 구성된다. 루트 디렉터리는 트리의 루트이고, 시스템 안의 각 파일 또는 폴더는 하나의 노드이다. 폴더는 자식 노드로 하위 폴더 또는 파일을 가질 수 있으며, 이러한 구조는 파일의 정리, 탐색, 검색을 효율적으로 가능하게 한다. 컴퓨터에서 폴더를 탐색할 때, 본질적으로는 트리 구조를 탐색하고 있는 것이다.

예제 문제

Invert Binary Tree

이진 트리를 뒤집고 그 루트를 반환하라. 이진 트리가 뒤집히면, 자기 자신의 거울상(mirror image)이 된다.

SiliconValley_survivor