Medium: Trees & Graphs (21-30)
Trees and graphs are particularly important for AI engineers. Graph neural networks, knowledge graphs, computational graphs (autograd), and decision trees all rely on the traversal and manipulation patterns covered here. These ten problems build your BFS, DFS, and tree recursion skills.
Problem 21: Binary Tree Level Order Traversal
LeetCode #102 — Given the root of a binary tree, return the level order traversal of its nodes' values (left to right, level by level).
Pattern: BFS with Queue — Process one level at a time using a queue.
ML Context: Level-order traversal is used in beam search decoding for sequence-to-sequence models. Each level of the search tree represents one time step of decoding.
from collections import deque
def levelOrder(root):
"""
Time: O(n) - visit every node
Space: O(n) - queue holds at most one level
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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
# Input: [3,9,20,null,null,15,7]
# Output: [[3],[9,20],[15,7]]Problem 22: Validate Binary Search Tree
LeetCode #98 — Given the root of a binary tree, determine if it is a valid BST.
Pattern: DFS with Range — Pass valid range (min, max) down the recursion.
ML Context: BST validation logic appears in decision tree construction. Each split must maintain ordering constraints, and validation ensures the tree structure is correct after pruning.
def isValidBST(root):
"""
Time: O(n) - visit every node
Space: O(h) - recursion depth equals tree height
"""
def validate(node, low, high):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))Problem 23: Number of Islands
LeetCode #200 — Given an m x n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Pattern: DFS/BFS Flood Fill — For each unvisited land cell, run DFS to mark the entire connected component.
ML Context: Connected component analysis is used in image segmentation (finding contiguous regions), clustering in graph-based methods, and identifying communities in social network graphs.
def numIslands(grid):
"""
Time: O(m * n) - visit every cell
Space: O(m * n) - recursion stack in worst case
"""
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' # mark visited
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
# numIslands([["1","1","0"],["1","1","0"],["0","0","1"]]) -> 2Problem 24: Course Schedule
LeetCode #207 — There are numCourses courses labeled 0 to numCourses - 1. You are given prerequisites pairs. Return whether you can finish all courses (i.e., no circular dependency).
Pattern: Topological Sort (BFS/Kahn's Algorithm) — Detect cycles in a directed graph.
ML Context: ML pipeline orchestration (Airflow, Kubeflow) uses topological sorting to determine task execution order. Dependency resolution in model training DAGs is exactly this problem.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
"""
Kahn's Algorithm (BFS Topological Sort)
Time: O(V + E) where V = courses, E = prerequisites
Space: O(V + E) for graph and queue
"""
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
completed = 0
while queue:
node = queue.popleft()
completed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return completed == numCourses
# canFinish(2, [[1,0]]) -> True
# canFinish(2, [[1,0],[0,1]]) -> False (cycle)Problem 25: Word Search
LeetCode #79 — Given an m x n grid of characters and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically).
Pattern: Backtracking DFS — Try each direction, mark visited, backtrack if dead end.
ML Context: Backtracking search appears in constraint satisfaction problems, beam search with pruning, and architecture search (NAS) where you explore and prune neural architecture candidates.
def exist(board, word):
"""
Time: O(m * n * 4^L) where L is word length
Space: O(L) recursion depth
"""
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[idx]):
return False
temp = board[r][c]
board[r][c] = '#' # mark visited
found = (dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1) or
dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1))
board[r][c] = temp # backtrack
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return FalseProblem 26: Clone Graph
LeetCode #133 — Given a reference of a node in a connected undirected graph, return a deep copy of the graph.
Pattern: BFS/DFS + Hash Map — Map original nodes to clones; traverse and copy edges.
ML Context: Deep copying graph structures is essential when creating model checkpoints, forking computational graphs for parallel experiments, or implementing graph neural network message passing.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def cloneGraph(node):
"""
Time: O(V + E) - visit every node and edge
Space: O(V) - hash map of clones
"""
if not node:
return None
clones = {}
def dfs(n):
if n in clones:
return clones[n]
clone = Node(n.val)
clones[n] = clone
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)Problem 27: Binary Tree Paths
LeetCode #257 — Given the root of a binary tree, return all root-to-leaf paths in any order.
Pattern: DFS with Path Tracking — Build path string during recursion, add to result at leaves.
ML Context: Path enumeration in decision trees is used for rule extraction — converting a trained decision tree into human-readable if-then rules for model interpretability.
def binaryTreePaths(root):
"""
Time: O(n) - visit every node
Space: O(n * h) - store paths, each up to height h
"""
if not root:
return []
paths = []
def dfs(node, path):
if not node.left and not node.right:
paths.append(path + str(node.val))
return
if node.left:
dfs(node.left, path + str(node.val) + "->")
if node.right:
dfs(node.right, path + str(node.val) + "->")
dfs(root, "")
return paths
# Input: [1,2,3,null,5]
# Output: ["1->2->5", "1->3"]Problem 28: Kth Smallest Element in a BST
LeetCode #230 — Given the root of a BST and an integer k, return the kth smallest value in the tree.
Pattern: Inorder Traversal — BST inorder gives sorted order; return the k-th element.
ML Context: Finding k-th order statistics efficiently is used in percentile computation for feature normalization, outlier detection thresholds, and quantile regression.
def kthSmallest(root, k):
"""
Iterative inorder traversal, stop at k-th element.
Time: O(H + k) where H is tree height
Space: O(H) for stack
"""
stack = []
current = root
count = 0
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
count += 1
if count == k:
return current.val
current = current.rightProblem 29: Serialize and Deserialize Binary Tree
LeetCode #297 — Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree structure.
Pattern: Preorder Traversal with null markers — Serialize with preorder DFS, use markers for null nodes.
ML Context: Model serialization (saving/loading) is critical in ML. PyTorch's torch.save and TensorFlow's SavedModel both serialize complex graph structures, similar to this problem.
class Codec:
def serialize(self, root):
"""
Preorder DFS serialization.
Time: O(n), Space: O(n)
"""
result = []
def dfs(node):
if not node:
result.append("null")
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(result)
def deserialize(self, data):
"""
Reconstruct tree from preorder serialization.
Time: O(n), Space: O(n)
"""
values = iter(data.split(","))
def dfs():
val = next(values)
if val == "null":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
return dfs()Problem 30: Lowest Common Ancestor
LeetCode #236 — Given a binary tree, find the lowest common ancestor (LCA) of two given nodes.
Pattern: Recursive DFS — If both subtrees return non-null, current node is LCA.
ML Context: LCA queries appear in taxonomy and ontology systems used by NLP models for entity linking and hierarchical classification. Finding the most specific common category of two entities is an LCA problem.
def lowestCommonAncestor(root, p, q):
"""
Time: O(n) - visit every node in worst case
Space: O(h) - recursion depth
"""
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 and q are in different subtrees
return left or right # both in same subtreeKey Takeaways
- BFS (Level Order, Course Schedule) is the right choice when you need level-by-level processing or shortest paths in unweighted graphs.
- DFS (Islands, Word Search, LCA) is the right choice for exhaustive search, path finding, and problems on tree structure.
- Topological sort (Course Schedule) solves dependency ordering — one of the most practical algorithms for ML pipeline engineering.
- BST properties (Validate BST, Kth Smallest) enable O(h) operations by leveraging sorted order.
- Trees and graphs are especially important for AI engineers because computational graphs, knowledge graphs, and GNNs are all built on these structures.