Coding Medium: Trees & Graphs
Difficulty: Medium | Companies: Google, Meta, Amazon, Netflix, Stripe
Binary Tree Traversals
from typing import List, Optional
from collections import deque
class TreeNode:
def __init__(self, val: int = 0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
"""Inorder traversal: Left -> Root -> Right.
Time: O(n), Space: O(h) where h is height
"""
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 preorder_traversal(root: Optional[TreeNode]) -> List[int]:
"""Preorder traversal: Root -> Left -> Right.
Time: O(n), Space: O(h)
"""
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
def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
"""Level order traversal (BFS).
Time: O(n), Space: O(n)
"""
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
def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
"""Zigzag level order traversal.
Time: O(n), Space: O(n)
"""
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
current_level = deque()
for _ in range(level_size):
node = queue.popleft()
if left_to_right:
current_level.append(node.val)
else:
current_level.appendleft(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(list(current_level))
left_to_right = not left_to_right
return result
βΉοΈ
For tree problems, consider both recursive and iterative approaches. Iterative solutions often use explicit stacks to simulate recursion.
Binary Search Trees
class BST:
"""Binary Search Tree implementation."""
def __init__(self):
self.root = None
def insert(self, val: int) -> None:
self.root = self._insert(self.root, val)
def _insert(self, node: Optional[TreeNode], val: int) -> TreeNode:
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def search(self, val: int) -> bool:
return self._search(self.root, val)
def _search(self, node: Optional[TreeNode], val: int) -> bool:
if not node:
return False
if val == node.val:
return True
elif val < node.val:
return self._search(node.left, val)
else:
return self._search(node.right, val)
def delete(self, val: int) -> None:
self.root = self._delete(self.root, val)
def _delete(self, node: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# Node with only one child or no child
if not node.left:
return node.right
elif not node.right:
return node.left
# Node with two children: Get inorder successor
node.val = self._min_value(node.right)
node.right = self._delete(node.right, node.val)
return node
def _min_value(self, node: TreeNode) -> int:
current = node
while current.left:
current = current.left
return current.val
def is_valid_bst(self) -> bool:
return self._validate(self.root, float('-inf'), float('inf'))
def _validate(self, node: Optional[TreeNode], min_val: float, max_val: float) -> bool:
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (self._validate(node.left, min_val, node.val) and
self._validate(node.right, node.val, max_val))
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""Find LCA of two nodes in BST.
Time: O(h), Space: O(h)
"""
current = root
while current:
if p.val < current.val and q.val < current.val:
current = current.left
elif p.val > current.val and q.val > current.val:
current = current.right
else:
return current
return None
def kth_smallest(root: TreeNode, k: int) -> int:
"""Find kth smallest element in BST.
Time: O(k + h), Space: O(h)
"""
stack = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right
return -1
β οΈ
When validating BST, always check with min/max bounds, not just that left < node < right. The left subtree's rightmost node must also be less than the root.
Graph Algorithms
from typing import List, Dict, Set
from collections import defaultdict, deque
class Graph:
"""Graph representation using adjacency list."""
def __init__(self, directed: bool = False):
self.graph = defaultdict(list)
self.directed = directed
self.vertices = set()
def add_edge(self, u: int, v: int, weight: int = 1):
self.graph[u].append((v, weight))
self.vertices.add(u)
self.vertices.add(v)
if not self.directed:
self.graph[v].append((u, weight))
def bfs(self, start: int) -> List[int]:
"""Breadth-first search.
Time: O(V + E), Space: O(V)
"""
visited = {start}
queue = deque([start])
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor, _ in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
def dfs(self, start: int) -> List[int]:
"""Depth-first search (iterative).
Time: O(V + E), Space: O(V)
"""
visited = {start}
stack = [start]
result = []
while stack:
vertex = stack.pop()
result.append(vertex)
for neighbor, _ in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return result
def has_path(self, source: int, destination: int) -> bool:
"""Check if path exists between source and destination."""
if source == destination:
return True
visited = {source}
queue = deque([source])
while queue:
vertex = queue.popleft()
for neighbor, _ in self.graph[vertex]:
if neighbor == destination:
return True
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False
def detect_cycle(self) -> bool:
"""Detect cycle in directed graph using DFS."""
WHITE, GRAY, BLACK = 0, 1, 2
color = {v: WHITE for v in self.vertices}
def dfs_cycle(vertex: int) -> bool:
color[vertex] = GRAY
for neighbor, _ in self.graph[vertex]:
if color[neighbor] == GRAY:
return True
if color[neighbor] == WHITE and dfs_cycle(neighbor):
return True
color[vertex] = BLACK
return False
for vertex in self.vertices:
if color[vertex] == WHITE:
if dfs_cycle(vertex):
return True
return False
def topological_sort_kahn(graph: Graph) -> List[int]:
"""Topological sort using Kahn's algorithm (BFS).
Time: O(V + E), Space: O(V)
"""
in_degree = defaultdict(int)
for vertex in graph.vertices:
for neighbor, _ in graph.graph[vertex]:
in_degree[neighbor] += 1
queue = deque([v for v in graph.vertices if in_degree[v] == 0])
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor, _ in graph.graph[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(graph.vertices):
raise ValueError("Graph has a cycle")
return result
def course_schedule(num_courses: int, prerequisites: List[List[int]]) -> bool:
"""Determine if all courses can be finished (cycle detection).
Time: O(V + E), Space: O(V)
"""
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
count = 0
while queue:
vertex = queue.popleft()
count += 1
for neighbor in graph[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == num_courses
# Test cases
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
print(graph.bfs(0)) # [0, 1, 2, 3]
print(graph.dfs(0)) # [0, 2, 3, 1]
print(course_schedule(2, [[1, 0]])) # True
Binary Tree Construction
def build_tree_from_preorder_inorder(
preorder: List[int], inorder: List[int]
) -> Optional[TreeNode]:
"""Construct binary tree from preorder and inorder traversals.
Time: O(n), Space: O(n)
"""
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = build_tree_from_preorder_inorder(preorder[1:mid + 1], inorder[:mid])
root.right = build_tree_from_preorder_inorder(preorder[mid + 1:], inorder[mid + 1:])
return root
def serialize(root: Optional[TreeNode]) -> str:
"""Serialize binary tree to string."""
if not root:
return "null"
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(data: str) -> Optional[TreeNode]:
"""Deserialize string to binary tree."""
if data == "null":
return None
values = data.split(',')
root = TreeNode(int(values[0]))
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
if 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
def is_symmetric(root: Optional[TreeNode]) -> bool:
"""Check if binary tree is symmetric.
Time: O(n), Space: O(h)
"""
def is_mirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_mirror(t1.left, t2.right) and
is_mirror(t1.right, t2.left))
return is_mirror(root, root) if root else True
# Test cases
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
tree = build_tree_from_preorder_inorder(preorder, inorder)
print(level_order_traversal(tree)) # [[3], [9, 20], [15, 7]]
serialized = serialize(tree)
print(serialized) # "3,9,20,null,null,15,7"
βΉοΈ
For tree construction problems, identify the root from one traversal and use the other to split left/right subtrees.
Follow-Up Questions
-
How would you find the diameter of a binary tree?
-
Explain the difference between BFS and DFS for graph problems.
-
How do you handle weighted graphs in shortest path algorithms?
-
When would you use Dijkstra's algorithm vs Bellman-Ford?
-
How do you find bridges and articulation points in a graph?