FAANG 코딩 인터뷰 완전 정복: 트리와 그래프 핵심 패턴

트리와 그래프 문제는 FAANG 인터뷰에서 배열/문자열 다음으로 출제 빈도가 높습니다. 특히 Google, Meta에서 그래프와 트리 탐색 문제를 매우 중요하게 봅니다. 이 글에서는 인터뷰 필수 패턴 5가지를 완전한 Python 코드와 함께 정복합니다.

1. Binary Tree 핵심 패턴

DFS (Depth-First Search)

DFS는 깊이 우선으로 트리를 탐색합니다. 재귀와 반복(스택) 두 가지 방식으로 구현할 수 있습니다.

트리 노드 정의

class TreeNode:

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

self.val = val

self.left = left

self.right = right

DFS 순회 3가지 (재귀)

Inorder: 왼쪽 → 현재 → 오른쪽 (BST에서 정렬된 순서)

def inorder(root):

if not root:

return []

return inorder(root.left) + [root.val] + inorder(root.right)

Preorder: 현재 → 왼쪽 → 오른쪽 (트리 복사, 직렬화)

def preorder(root):

if not root:

return []

return [root.val] + preorder(root.left) + preorder(root.right)

Postorder: 왼쪽 → 오른쪽 → 현재 (디렉토리 크기 계산)

def postorder(root):

if not root:

return []

return postorder(root.left) + postorder(root.right) + [root.val]

DFS 반복 구현 (스택 사용)

def inorderIterative(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

def preorderIterative(root):

if not root:

return []

result = []

stack = [root]

while stack:

node = stack.pop()

result.append(node.val)

오른쪽을 먼저 스택에 넣어야 왼쪽이 먼저 처리됨

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return result

BFS (Breadth-First Search) - Level Order Traversal

from collections import deque

def levelOrder(root):

if not root:

return []

result = []

queue = deque([root])

while queue:

level_size = len(queue)

current_level = []

for _ in range(level_size):

node = queue.popleft()

current_level.append(node.val)

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

result.append(current_level)

return result

예시

트리: 3

/ \

9 20

/ \

15 7

Output: [[3], [9,20], [15,7]]

문제 1: Maximum Depth of Binary Tree (LeetCode 104)

def maxDepth(root) -> int:

if not root:

return 0

return 1 + max(maxDepth(root.left), maxDepth(root.right))

BFS 방식

def maxDepthBFS(root) -> int:

if not root:

return 0

depth = 0

queue = deque([root])

while queue:

depth += 1

for _ in range(len(queue)):

node = queue.popleft()

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

return depth

**시간 복잡도:** O(n) - 모든 노드 방문

**공간 복잡도:** O(h) - h는 트리 높이 (최악 O(n) for skewed tree)

문제 2: Invert Binary Tree (LeetCode 226)

def invertTree(root):

if not root:

return None

왼쪽과 오른쪽 서브트리를 교환

root.left, root.right = invertTree(root.right), invertTree(root.left)

return root

반복 방식 (BFS)

def invertTreeBFS(root):

if not root:

return None

queue = deque([root])

while queue:

node = queue.popleft()

node.left, node.right = node.right, node.left

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

return root

**시간 복잡도:** O(n)

**공간 복잡도:** O(n) for balanced tree, O(n) worst case

문제 3: Symmetric Tree (LeetCode 101)

트리가 대칭인지 확인하라.

def isSymmetric(root) -> bool:

def isMirror(left, right):

if not left and not right:

return True

if not left or not right:

return False

return (left.val == right.val and

isMirror(left.left, right.right) and

isMirror(left.right, right.left))

return isMirror(root.left, root.right)

반복 방식

def isSymmetricIterative(root) -> bool:

queue = deque([(root.left, root.right)])

while queue:

left, right = queue.popleft()

if not left and not right:

continue

if not left or not right:

return False

if left.val != right.val:

return False

queue.append((left.left, right.right))

queue.append((left.right, right.left))

return True

문제 4: Path Sum II (LeetCode 113)

루트에서 리프까지 합이 targetSum이 되는 모든 경로를 찾아라.

def pathSum(root, targetSum: int):

result = []

def dfs(node, current_path, remaining):

if not node:

return

current_path.append(node.val)

remaining -= node.val

리프 노드이고 합이 맞으면 경로 추가

if not node.left and not node.right and remaining == 0:

result.append(list(current_path))

else:

dfs(node.left, current_path, remaining)

dfs(node.right, current_path, remaining)

백트래킹: 현재 노드 제거

current_path.pop()

dfs(root, [], targetSum)

return result

문제 5: Lowest Common Ancestor (LeetCode 236)

두 노드 p, q의 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)

양쪽에서 발견되면 현재 노드가 LCA

if left and right:

return root

한쪽에서만 발견되면 그쪽이 LCA

return left if left else right

예시

트리: 3

/ \

5 1

/ \ / \

6 2 0 8

/ \

7 4

p=5, q=1 → LCA = 3

p=5, q=4 → LCA = 5

문제 6: Serialize and Deserialize Binary Tree (LeetCode 297) - 고난도

class Codec:

def serialize(self, root) -> str:

"""BFS를 사용해 트리를 문자열로 직렬화"""

if not root:

return ""

result = []

queue = deque([root])

while queue:

node = queue.popleft()

if node:

result.append(str(node.val))

queue.append(node.left)

queue.append(node.right)

else:

result.append("null")

return ",".join(result)

def deserialize(self, data: str):

"""직렬화된 문자열에서 트리 복원"""

if not data:

return None

values = data.split(",")

root = TreeNode(int(values[0]))

queue = deque([root])

i = 1

while queue:

node = queue.popleft()

if i < len(values) and values[i] != "null":

node.left = TreeNode(int(values[i]))

queue.append(node.left)

i += 1

if i < len(values) and values[i] != "null":

node.right = TreeNode(int(values[i]))

queue.append(node.right)

i += 1

return root

**시간 복잡도:** O(n) - 모든 노드 방문

**공간 복잡도:** O(n) - 직렬화 결과 저장

2. Binary Search Tree (BST) 패턴

BST 특성

- 왼쪽 서브트리의 모든 값 < 현재 노드 값

- 오른쪽 서브트리의 모든 값 > 현재 노드 값

- Inorder 순회 시 정렬된 순서로 방문

문제 7: Validate Binary Search Tree (LeetCode 98)

def isValidBST(root) -> bool:

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'))

함정: 단순히 left.val < root.val < right.val 만 체크하는 것은 틀림

예시:

5

/ \

1 4

/ \

3 6

root.right.left = 3 (3 < 5 이므로 BST 위반)

문제 8: Kth Smallest Element in BST (LeetCode 230)

def kthSmallest(root, k: int) -> int:

Inorder 순회가 정렬된 순서이므로 k번째가 답

count = [0]

result = [0]

def inorder(node):

if not node or count[0] >= k:

return

inorder(node.left)

count[0] += 1

if count[0] == k:

result[0] = node.val

return

inorder(node.right)

inorder(root)

return result[0]

반복 방식 (더 직관적)

def kthSmallestIterative(root, k: int) -> int:

stack = []

current = root

while current or stack:

while current:

stack.append(current)

current = current.left

current = stack.pop()

k -= 1

if k == 0:

return current.val

current = current.right

return -1

문제 9: Convert Sorted Array to BST (LeetCode 108)

정렬된 배열을 높이 균형 BST로 변환하라.

def sortedArrayToBST(nums: list[int]):

def buildBST(left, right):

if left > right:

return None

중간 값을 루트로 선택 (균형 보장)

mid = left + (right - left) // 2

root = TreeNode(nums[mid])

root.left = buildBST(left, mid - 1)

root.right = buildBST(mid + 1, right)

return root

return buildBST(0, len(nums) - 1)

3. Graph BFS/DFS 패턴

그래프 표현

인접 리스트 (권장)

graph = {

0: [1, 2],

1: [0, 3],

2: [0, 4],

3: [1],

4: [2]

}

인접 행렬

matrix = [

[0, 1, 1, 0, 0],

[1, 0, 0, 1, 0],

[1, 0, 0, 0, 1],

[0, 1, 0, 0, 0],

[0, 0, 1, 0, 0]

]

방문 처리

DFS (재귀)

def dfs(graph, start, visited=None):

if visited is None:

visited = set()

visited.add(start)

print(start, end=' ')

for neighbor in graph[start]:

if neighbor not in visited:

dfs(graph, neighbor, visited)

BFS

def bfs(graph, start):

visited = set([start])

queue = deque([start])

while queue:

node = queue.popleft()

print(node, end=' ')

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor)

queue.append(neighbor)

문제 10: Number of Islands (LeetCode 200)

def numIslands(grid: list[list[str]]) -> int:

if not grid:

return 0

rows, cols = len(grid), len(grid[0])

count = 0

def dfs(r, c):

범위 벗어나거나 물이면 종료

if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':

return

방문 표시 (물로 변경)

grid[r][c] = '0'

4방향 탐색

dfs(r + 1, c)

dfs(r - 1, c)

dfs(r, c + 1)

dfs(r, c - 1)

for r in range(rows):

for c in range(cols):

if grid[r][c] == '1':

count += 1

dfs(r, c)

return count

예시

Input: grid = [

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

Output: 3

**시간 복잡도:** O(m*n)

**공간 복잡도:** O(m*n) - 재귀 스택

문제 11: Clone Graph (LeetCode 133)

class Node:

def __init__(self, val=0, neighbors=None):

self.val = val

self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):

if not node:

return None

cloned = {} # 원본 노드 → 복제 노드 매핑

def dfs(original):

if original in cloned:

return cloned[original]

복제 노드 생성

copy = Node(original.val)

cloned[original] = copy

이웃 재귀 복제

for neighbor in original.neighbors:

copy.neighbors.append(dfs(neighbor))

return copy

return dfs(node)

**시간 복잡도:** O(V + E) - 모든 정점과 간선 방문

**공간 복잡도:** O(V) - 복제 매핑 저장

문제 12: Course Schedule (LeetCode 207) - 위상 정렬

선수과목 관계가 주어질 때 모든 과목을 수강할 수 있는지 판별하라.

from collections import defaultdict, deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:

그래프 구성

graph = defaultdict(list)

in_degree = [0] * numCourses

for course, prereq in prerequisites:

graph[prereq].append(course)

in_degree[course] += 1

진입 차수가 0인 노드에서 시작 (선수과목 없는 과목)

queue = deque([i for i in range(numCourses) if in_degree[i] == 0])

completed = 0

while queue:

course = queue.popleft()

completed += 1

for next_course in graph[course]:

in_degree[next_course] -= 1

if in_degree[next_course] == 0:

queue.append(next_course)

모든 과목을 완료했으면 사이클 없음

return completed == numCourses

DFS로 사이클 감지

def canFinishDFS(numCourses: int, prerequisites: list[list[int]]) -> bool:

graph = defaultdict(list)

for course, prereq in prerequisites:

graph[prereq].append(course)

상태: 0=미방문, 1=방문중, 2=완료

state = [0] * numCourses

def hasCycle(node):

if state[node] == 1: # 사이클 발견

return True

if state[node] == 2: # 이미 처리됨

return False

state[node] = 1 # 방문 시작

for neighbor in graph[node]:

if hasCycle(neighbor):

return True

state[node] = 2 # 방문 완료

return False

for i in range(numCourses):

if hasCycle(i):

return False

return True

문제 13: Pacific Atlantic Water Flow (LeetCode 417)

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:

if not heights:

return []

rows, cols = len(heights), len(heights[0])

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def bfs(starts):

visited = set(starts)

queue = deque(starts)

while queue:

r, c = queue.popleft()

for dr, dc in directions:

nr, nc = r + dr, c + dc

if (0 <= nr < rows and 0 <= nc < cols and

(nr, nc) not in visited and

heights[nr][nc] >= heights[r][c]): # 역방향 탐색

visited.add((nr, nc))

queue.append((nr, nc))

return visited

태평양 (상단 + 좌측 경계)

pacific_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)]

대서양 (하단 + 우측 경계)

atlantic_starts = [(rows-1, c) for c in range(cols)] + [(r, cols-1) for r in range(rows-1)]

pacific = bfs(pacific_starts)

atlantic = bfs(atlantic_starts)

return [[r, c] for r, c in pacific & atlantic]

문제 14: Word Ladder (LeetCode 127)

BFS로 단어 변환 최단 경로를 구하라.

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:

word_set = set(wordList)

if endWord not in word_set:

return 0

queue = deque([(beginWord, 1)])

visited = {beginWord}

while queue:

word, steps = queue.popleft()

for i in range(len(word)):

for c in 'abcdefghijklmnopqrstuvwxyz':

new_word = word[:i] + c + word[i+1:]

if new_word == endWord:

return steps + 1

if new_word in word_set and new_word not in visited:

visited.add(new_word)

queue.append((new_word, steps + 1))

return 0

예시

beginWord = "hit", endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5 (hit→hot→dot→dog→cog)

**시간 복잡도:** O(M^2 _ N) - M은 단어 길이, N은 단어 수

**공간 복잡도:** O(M^2 _ N)

4. Union Find (Disjoint Set) 패턴

구현

class UnionFind:

def __init__(self, n):

self.parent = list(range(n)) # 각 노드의 부모

self.rank = [0] * n # 트리 높이

def find(self, x):

Path Compression

if self.parent[x] != x:

self.parent[x] = self.find(self.parent[x])

return self.parent[x]

def union(self, x, y):

px, py = self.find(x), self.find(y)

if px == py:

return False # 이미 같은 집합

Union by Rank

if self.rank[px] < self.rank[py]:

px, py = py, px

self.parent[py] = px

if self.rank[px] == self.rank[py]:

self.rank[px] += 1

return True

def connected(self, x, y):

return self.find(x) == self.find(y)

문제 15: Number of Connected Components (LeetCode 323)

def countComponents(n: int, edges: list[list[int]]) -> int:

uf = UnionFind(n)

components = n

for u, v in edges:

if uf.union(u, v):

components -= 1 # 두 컴포넌트가 합쳐지면 감소

return components

문제 16: Redundant Connection (LeetCode 684)

트리에 하나의 중복 간선이 추가되었을 때, 그 간선을 찾아라.

def findRedundantConnection(edges: list[list[int]]) -> list[int]:

n = len(edges)

uf = UnionFind(n + 1)

for u, v in edges:

if not uf.union(u, v):

return [u, v] # 이미 연결된 경우 → 중복 간선

return []

문제 17: Accounts Merge (LeetCode 721)

def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:

email_to_id = {} # 이메일 → ID

email_to_name = {} # 이메일 → 이름

모든 이메일에 고유 ID 부여

for i, account in enumerate(accounts):

name = account[0]

for email in account[1:]:

if email not in email_to_id:

email_to_id[email] = len(email_to_id)

email_to_name[email] = name

uf = UnionFind(len(email_to_id))

같은 계정의 이메일들을 Union

for account in accounts:

first_email = account[1]

first_id = email_to_id[first_email]

for email in account[2:]:

uf.union(first_id, email_to_id[email])

같은 그룹의 이메일들을 모음

from collections import defaultdict

groups = defaultdict(list)

for email, eid in email_to_id.items():

root = uf.find(eid)

groups[root].append(email)

result = []

for root, emails in groups.items():

name = email_to_name[emails[0]]

result.append([name] + sorted(emails))

return result

5. Shortest Path 알고리즘

Dijkstra's Algorithm

음수 가중치가 없는 그래프에서 단일 출발점 최단 경로를 구합니다.

from collections import defaultdict

def dijkstra(graph: dict, start: int) -> dict:

distances = {node: float('inf') for node in graph}

distances[start] = 0

priority_queue = [(0, start)] # (거리, 노드)

while priority_queue:

current_dist, current_node = heapq.heappop(priority_queue)

더 짧은 경로가 이미 있으면 스킵

if current_dist > distances[current_node]:

continue

for neighbor, weight in graph[current_node]:

distance = current_dist + weight

if distance < distances[neighbor]:

distances[neighbor] = distance

heapq.heappush(priority_queue, (distance, neighbor))

return distances

예시

graph = {

0: [(1, 4), (2, 1)],

1: [(3, 1)],

2: [(1, 2), (3, 5)],

3: []

}

distances from 0: {0: 0, 1: 3, 2: 1, 3: 4}

**시간 복잡도:** O((V + E) log V)

**공간 복잡도:** O(V)

문제 18: Network Delay Time (LeetCode 743)

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:

graph = defaultdict(list)

for u, v, w in times:

graph[u].append((v, w))

distances = {i: float('inf') for i in range(1, n + 1)}

distances[k] = 0

pq = [(0, k)]

while pq:

dist, node = heapq.heappop(pq)

if dist > distances[node]:

continue

for neighbor, weight in graph[node]:

new_dist = dist + weight

if new_dist < distances[neighbor]:

distances[neighbor] = new_dist

heapq.heappush(pq, (new_dist, neighbor))

max_dist = max(distances.values())

return max_dist if max_dist != float('inf') else -1

예시

times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2

Output: 2

문제 19: Cheapest Flights Within K Stops (LeetCode 787)

Bellman-Ford 변형으로 k번 이하 경유지로 최저 비용을 구합니다.

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:

Bellman-Ford: k+1번 릴랙세이션

prices = [float('inf')] * n

prices[src] = 0

for i in range(k + 1):

temp = prices.copy() # 현재 단계 결과를 분리

for u, v, w in flights:

if prices[u] != float('inf') and prices[u] + w < temp[v]:

temp[v] = prices[u] + w

prices = temp

return prices[dst] if prices[dst] != float('inf') else -1

예시

n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1

Output: 200 (0→1→2)

6. FAANG 기업별 트리/그래프 출제 경향

Google

Google은 **그래프 문제를 매우 자주** 출제합니다.

- 자주 출제: 그래프 탐색, 위상 정렬, 최단 경로

- 핵심: 효율적인 알고리즘 선택과 복잡도 분석

- 예시 문제: Course Schedule II, Word Ladder, Alien Dictionary

Meta (Facebook)

Meta는 **Tree Traversal과 LCA** 문제를 선호합니다.

- 자주 출제: Binary Tree, LCA, Serialize/Deserialize

- 핵심: 재귀와 반복 두 방식 모두 구현 가능

- 예시 문제: Binary Tree Right Side View, Vertical Order Traversal

Amazon

Amazon은 **BFS/최단 경로** 문제를 많이 출제합니다.

- 자주 출제: Number of Islands, BFS 변형, Union Find

- 핵심: 실용적이고 효율적인 해법

- 예시 문제: Rotting Oranges, Find if Path Exists in Graph

7. 연습 문제 퀴즈

이진 트리에서 임의의 두 노드 사이의 최장 경로 길이(간선 수)를 구하라. 경로가 루트를 통과하지 않아도 됩니다.

**정답**: DFS로 각 노드에서 왼쪽/오른쪽 최대 깊이의 합을 계산하고 전역 최대값을 업데이트합니다.

**설명**:

def diameterOfBinaryTree(root) -> int:

max_diameter = [0]

def depth(node):

if not node:

return 0

left_depth = depth(node.left)

right_depth = depth(node.right)

현재 노드를 지나는 경로의 지름

max_diameter[0] = max(max_diameter[0], left_depth + right_depth)

return 1 + max(left_depth, right_depth)

depth(root)

return max_diameter[0]

방향 그래프 `graph = {0: [1], 1: [2], 2: [0], 3: [4], 4: []}`에서 사이클이 있는가?

**정답**: Yes (0 → 1 → 2 → 0)

**설명**: DFS와 색상 마킹(0=미방문, 1=방문중, 2=완료)을 사용합니다. 방문 중인 노드를 다시 만나면 사이클입니다.

def hasCycle(graph):

state = {}

def dfs(node):

if state.get(node) == 1:

return True # 사이클

if state.get(node) == 2:

return False # 이미 처리

state[node] = 1

for neighbor in graph.get(node, []):

if dfs(neighbor):

return True

state[node] = 2

return False

return any(dfs(node) for node in graph if node not in state)

BST와 타겟 k가 주어질 때 두 노드 값의 합이 k가 되는 경우가 있는지 판별하라.

**정답**: Inorder 순회로 정렬된 값들을 얻은 후 Two Pointers를 적용합니다.

**설명**:

def findTarget(root, k: int) -> bool:

def inorder(node):

if not node:

return []

return inorder(node.left) + [node.val] + inorder(node.right)

nums = inorder(root)

left, right = 0, len(nums) - 1

while left < right:

total = nums[left] + nums[right]

if total == k:

return True

elif total < k:

left += 1

else:

right -= 1

return False

이진 그리드에서 1로 연결된 섬 중 가장 큰 섬의 넓이를 구하라.

**정답**: DFS/BFS로 각 섬의 넓이를 계산하고 최대값을 반환합니다.

**설명**:

def maxAreaOfIsland(grid):

rows, cols = len(grid), len(grid[0])

def dfs(r, c):

if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:

return 0

grid[r][c] = 0 # 방문 표시

return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)

return max(dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c])

Union Find를 이용해 n개의 도시를 최소 비용으로 연결하는 알고리즘을 구현하라. (Min Cost to Connect All Points, LeetCode 1584)

**정답**: 모든 간선을 비용 오름차순으로 정렬 후, Union Find로 사이클 없이 간선을 추가합니다.

**설명**:

def minCostConnectPoints(points):

n = len(points)

모든 간선 생성 (맨해튼 거리)

edges = []

for i in range(n):

for j in range(i + 1, n):

dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

edges.append((dist, i, j))

edges.sort()

uf = UnionFind(n)

total_cost = 0

edges_used = 0

for cost, u, v in edges:

if uf.union(u, v):

total_cost += cost

edges_used += 1

if edges_used == n - 1:

break

return total_cost

마무리

트리와 그래프는 FAANG 인터뷰에서 가장 다양한 패턴이 등장하는 분야입니다. 특히:

- **DFS/BFS 선택**: 최단 경로 → BFS, 모든 경로 탐색 → DFS

- **트리 문제**: 재귀가 자연스러운 경우가 많음, 반복도 준비

- **그래프 문제**: visited 처리를 항상 명확히 하기

- **Union Find**: 연결성 문제에서 강력한 도구

**추천 LeetCode 목록:**

- Easy: Maximum Depth, Invert Tree, Symmetric Tree

- Medium: Course Schedule, Number of Islands, LCA, BFS/DFS 변형

- Hard: Serialize/Deserialize, Word Ladder II, Alien Dictionary