Patterns & Tips
This final lesson consolidates everything into a reference you can use during practice and before interviews. The pattern cheat sheet maps problem types to algorithms, the visualization guide helps you debug, and the FAQ covers the most common questions from students and interviewers.
Tree Pattern Cheat Sheet
| If You See... | Think... | Algorithm | Time |
|---|---|---|---|
| "Sorted order from tree" | Inorder traversal of BST | DFS inorder | O(n) |
| "Copy/serialize tree" | Preorder with null markers | DFS preorder | O(n) |
| "Process children before parent" | Postorder (like backprop) | DFS postorder | O(n) |
| "Level by level" or "minimum depth" | BFS level-order | BFS with queue | O(n) |
| "Validate BST" | Inorder must be strictly increasing | DFS with bounds | O(n) |
| "LCA in BST" | First node where paths diverge | BST property | O(h) |
| "Max depth / height" | Recursive: 1 + max(left, right) | DFS | O(n) |
| "Path sum / root to leaf" | DFS with running sum | DFS + backtrack | O(n) |
| "Build tree from traversals" | Root from preorder, split from inorder | Divide and conquer | O(n) |
| "Autocomplete / prefix search" | Trie | Trie insert/search | O(L) |
Graph Pattern Cheat Sheet
| If You See... | Think... | Algorithm | Time |
|---|---|---|---|
| "Shortest path, unweighted" | BFS | BFS | O(V + E) |
| "Shortest path, non-negative weights" | Dijkstra | Min-heap BFS | O((V+E) log V) |
| "Shortest path, negative weights" | Bellman-Ford | Relax V-1 times | O(V * E) |
| "Shortest path in DAG" | Topological sort + relaxation | Topo sort | O(V + E) |
| "Dependencies / ordering" | Topological sort | Kahn's or DFS | O(V + E) |
| "Cycle detection (directed)" | DFS with 3 colors | DFS | O(V + E) |
| "Cycle detection (undirected)" | Union-Find or DFS | Union-Find | O(E * alpha) |
| "Connected components" | BFS/DFS from unvisited nodes | BFS or Union-Find | O(V + E) |
| "Number of islands / regions" | Flood fill (BFS/DFS on grid) | BFS/DFS | O(m * n) |
| "Minimum spanning tree" | Kruskal (sort edges) or Prim (grow tree) | Kruskal/Prim | O(E log E) |
| "Dynamic connectivity" | Union-Find | DSU | O(alpha) per op |
Visualization Tips for Debugging
# Quick tree printer for debugging
def print_tree(root, level=0, prefix="Root: "):
"""Print tree structure for debugging during practice."""
if not root:
return
print(" " * (level * 4) + prefix + str(root.val))
if root.left or root.right:
if root.left:
print_tree(root.left, level + 1, "L--- ")
else:
print(" " * ((level + 1) * 4) + "L--- None")
if root.right:
print_tree(root.right, level + 1, "R--- ")
else:
print(" " * ((level + 1) * 4) + "R--- None")
# Quick graph printer for debugging
def print_graph(graph, directed=True):
"""Print graph adjacency list for debugging."""
arrow = " -> " if directed else " -- "
for node in sorted(graph):
neighbors = ", ".join(str(n) for n in graph[node])
print(f" {node}{arrow}[{neighbors}]")
# Quick BFS state tracker
def bfs_debug(graph, start):
"""BFS with step-by-step state printing."""
from collections import deque
visited = {start}
queue = deque([start])
step = 0
while queue:
step += 1
node = queue.popleft()
neighbors = [n for n in graph[node] if n not in visited]
print(f"Step {step}: Visit {node}, "
f"Queue: {list(queue)}, "
f"New neighbors: {neighbors}")
for n in neighbors:
visited.add(n)
queue.append(n)Common Mistakes to Avoid
1. Forgetting Base Cases
Always handle if not root: return for trees and empty graph checks. Missing base cases cause infinite recursion or NoneType errors. Write the base case first, then the recursive case.
2. Not Tracking Visited Nodes
In graphs (unlike trees), you can revisit nodes. Forgetting the visited set in BFS/DFS causes infinite loops. Always mark a node as visited when you add it to the queue/stack, not when you process it.
3. BST Validation Error
Checking only left.val < node.val < right.val is insufficient. You must track the valid range for each subtree. The value [5, 1, 6, null, null, 3, 7] fails the simple check because 3 is in the right subtree of 5.
4. Modifying Input During Traversal
Changing the grid/graph while iterating can cause issues. For "number of islands", marking cells as visited by changing '1' to '0' is fine, but be aware that you are destroying the input. Make a copy if the caller needs the original.
5. Wrong Dijkstra Implementation
Two common Dijkstra bugs: (1) Not skipping stale heap entries (if d > dist[u]: continue), which causes incorrect results. (2) Using Dijkstra with negative weights, which does not work — use Bellman-Ford instead.
6. Stack Overflow on Deep Trees
Python's default recursion limit is 1000. For trees with depth > 1000 (skewed trees, linked-list-like), recursive DFS will crash. Use iterative DFS with an explicit stack, or increase the limit with sys.setrecursionlimit().
Interview Approach Template
# Step-by-step approach for tree/graph problems in interviews:
# 1. CLARIFY (1-2 minutes)
# - Is it a tree or general graph?
# - Directed or undirected?
# - Weighted or unweighted?
# - Can there be cycles?
# - What are the node values (integers, strings)?
# - What to return (boolean, list, count)?
# 2. IDENTIFY PATTERN (1 minute)
# - Match to cheat sheet above
# - State the algorithm: "This is a BFS shortest path problem"
# - State complexity: "O(V + E) time, O(V) space"
# 3. WALK THROUGH EXAMPLE (2-3 minutes)
# - Draw the tree/graph
# - Trace algorithm on small example
# - Verify output matches expected
# 4. CODE (10-15 minutes)
# - Write clean, modular code
# - Use descriptive variable names
# - Add brief comments for key logic
# 5. TEST (2-3 minutes)
# - Trace through your code with the example
# - Test edge cases: empty input, single node, linear tree
# - Verify time/space complexityFrequently Asked Questions
Use recursive when: the problem naturally decomposes into subproblems on left/right subtrees (most tree problems), and the tree depth is bounded (less than ~1000). Use iterative when: the tree can be very deep (risk of stack overflow), you need fine-grained control over traversal order, or the problem requires BFS (level-order). In interviews, start with recursive (cleaner code), then mention you would use iterative for production code to avoid stack overflow. Most interviewers prefer recursive for clarity.
BFS: shortest path in unweighted graphs, level-by-level processing, finding the nearest node satisfying a condition. DFS: cycle detection, topological sort, finding all paths, backtracking problems, connected components (either works but DFS is often simpler). Memory consideration: BFS stores the entire frontier (can be O(V) for wide graphs), DFS stores the current path (O(depth)). For very wide graphs, DFS uses less memory; for very deep graphs, BFS is safer.
Always iterate through all nodes and start BFS/DFS from any unvisited node. The pattern is: for node in range(n): if node not in visited: bfs_or_dfs(node). Each call to BFS/DFS processes one connected component. This is how "number of islands" and "connected components" problems work. Never assume the graph is connected unless the problem explicitly states it.
Use defaultdict(list) for adjacency lists (90% of problems). For weighted graphs, store tuples: graph[u].append((v, weight)). Use a set instead of list when you need O(1) neighbor lookup: defaultdict(set). Use an adjacency matrix only for dense graphs or when the algorithm requires it (Floyd-Warshall). For Union-Find problems, you do not need an explicit graph — just the parent array.
ML interviews test tree/graph skills in several ways: (1) Implement a decision tree from scratch — requires tree construction and traversal. (2) Design an ML pipeline DAG — requires topological sort and cycle detection. (3) Knowledge graph querying — requires BFS/DFS and shortest path. (4) Feature engineering on graphs — compute PageRank, node centrality, community detection. (5) Computation graph questions — explain how autograd traverses the graph for backpropagation (reverse topological order = postorder).
Focus on quality over quantity. Solve 15-20 problems covering these core patterns: (1) all 4 traversals, (2) BST validation and search, (3) BFS shortest path, (4) DFS cycle detection, (5) topological sort, (6) Dijkstra, (7) Union-Find. If you can solve one problem from each pattern without looking at hints, you are well-prepared. The 32 problems in this course cover all these patterns. Re-solve problems you struggled with after 2-3 days to cement the patterns.
Based on frequency: (1) Number of Islands (BFS/DFS on grid), (2) Course Schedule (topological sort), (3) Validate BST, (4) LCA of Binary Tree, (5) Clone Graph (BFS with hash map), (6) Word Ladder (BFS shortest path), (7) Serialize/Deserialize Tree, (8) Trie implementation. All of these are covered in this course. At ML-focused companies (Google Brain, Meta AI), also expect computation graph and pipeline DAG questions.
Course Summary
You have completed Trees & Graphs for AI. Here is what you can now do:
- Traverse any binary tree using inorder, preorder, postorder, and level-order approaches
- Solve BST problems using the sorted property for O(h) operations
- Apply BFS for shortest paths and DFS for cycle detection and exhaustive search
- Use topological sort to resolve dependencies in ML pipelines and build systems
- Implement Dijkstra for weighted shortest paths and Union-Find for dynamic connectivity
- Build trees from traversal data, serialize/deserialize for model storage, and implement tries for prefix search
- Connect every algorithm to real AI/ML applications: decision trees, computation graphs, DAGs, knowledge graphs
Next steps: Practice the 32 problems without looking at solutions. Time yourself (aim for 20-30 minutes per problem). Review problems you could not solve after 2-3 days. Good luck with your interviews.