Lab: graphs and trees
Four checkpoints — BFS shortest path, connected components, BST insert with inorder verification, and BST search.
- Implement BFS to return the shortest path between two nodes
- Count connected components in an undirected graph using DFS
- Implement BST insert and verify sortedness with inorder traversal
- Implement BST search returning True or False
This is an optional lab. Four checkpoints, two on graphs and two on trees. Each one applies a technique from the last three lessons to a concrete problem. Work through the starter code before reading ahead.
Checkpoint 1 — BFS shortest path
BFS visits nodes level by level, so the first time it reaches a node it has found the shortest route. Track the path by storing full routes in the queue: each entry is the sequence of nodes visited so far.
Implement bfs_path(graph, start, goal) returning the shortest path from start to goal as a list of nodes, or an empty list if no path exists. If start == goal return [start]. graph is an adjacency dict: {node: [neighbour, ...]}.
bfs_path({0:[1,2],1:[0,3],2:[0],3:[1]}, 0, 3) → [0, 1, 3]bfs_path({0:[1],1:[0],2:[3],3:[2]}, 0, 2) → []The visited set is updated when a node is enqueued, not dequeued. If you
wait until dequeue, the same node can be added to the queue multiple times
from different neighbours — correct results but wasted memory and time.
Checkpoint 2 — Connected components
An undirected graph may have several disconnected pieces. Iterate over every node; whenever you find an unvisited one, a new component starts. Use DFS (iterative with a stack) to mark every node in that component before moving on.
Implement count_components(graph) returning the number of connected components in the undirected graph. graph is an adjacency dict where each undirected edge appears in both directions.
count_components({0:[1,2],1:[0],2:[0],3:[4],4:[3]}) → 2count_components({0:[],1:[],2:[]}) → 3The outer loop over all nodes guarantees no node is skipped. The inner DFS
only runs when node not in visited, so each node triggers at most one
component count. Total time: O(V + E).
Checkpoint 3 — BST insert and inorder
Insert values into a BST one at a time, then verify the BST invariant by checking that inorder traversal returns all values in sorted order.
Implement insert(root, val) that inserts val into the BST and returns the (possibly new) root, and inorder(root) that returns node values in sorted order as a list. Duplicate values should be ignored.
insert values [5,3,7,1,4], then inorder → [1, 3, 4, 5, 7]Inserting values 1–5 in sorted order produces a right-skewed tree of height 5, but inorder traversal still gives the correct sorted output. The invariant holds regardless of shape — shape affects speed (O(n) instead of O(log n)), not correctness.
Checkpoint 4 — BST search
Search descends the tree using the BST invariant: go left if the target is
smaller, go right if larger, return True when found, False when you reach
a None node.
Implement search(root, val) returning True if val is in the BST rooted at root, False otherwise.
search(bst with [5,3,7,1,4,6,8], 4) → Truesearch(bst with [5,3,7,1,4,6,8], 9) → FalseEach comparison eliminates one subtree. In a balanced tree of n nodes the search takes O(log n) steps. In the worst case — sorted insertion — it degrades to O(n). The algorithm is identical to binary search on a sorted array; the BST is just that binary search encoded as a data structure.
Done?
Four checkpoints, two data structures. BFS shortest path and connected components are graph traversal problems where the queue (BFS) and stack (DFS) determine the visit order and properties. BST insert and search are both applications of the same binary-search logic: at each node, discard the irrelevant half of the tree and recurse into the relevant one. The inorder check in checkpoint 3 is not just a test — it is a proof that the BST invariant is maintained through every insertion.
Binary search trees
Define the BST invariant, understand O(log n) average search and insertion, and see why balance matters when sorted input degrades a BST to O(n).
DP intuition
Understand why naive recursion explodes exponentially and how dynamic programming avoids redundant work by storing subproblem results.