Module 07: Recursion, trees and graphs

A recursive function calls itself on a smaller subproblem. A base case returns without another call. For factorial, fact(0)=1 and fact(n)=n×fact(n−1) for nonnegative n. Each pending call keeps local state on the call stack; returning unwinds those frames. Show that a nonnegative measure decreases, otherwise a base case alone does not guarantee termination. Deep recursion also consumes stack memory; Python limits depth, so an iterative solution or explicit stack may be preferable for large inputs.

A rooted tree has a distinguished root and parent-child structure without cycles. A binary tree has at most two children per node. Preorder visits node, left, right; inorder visits left, node, right; postorder visits left, right, node. In a binary search tree, all left keys precede the node and right keys follow it, so inorder yields sorted keys. Height controls search cost: balanced trees have logarithmic height, while a chain can have linear height. The lab constructs immutable nested tuples rather than a full mutable search-tree implementation.

A graph has vertices and edges. Edges may be directed, undirected or weighted. An adjacency list stores neighbours for each vertex, using O(V+E) storage in the usual model; an adjacency matrix uses O(V²) and supports direct edge checks. Unlike a tree, a graph can have cycles and multiple paths, so traversal needs visited state. Mark a vertex when scheduling it to avoid adding the same vertex repeatedly. Specify whether isolated vertices, unknown endpoints and parallel edges are allowed.

Depth-first search follows a branch before alternatives, using recursion or an explicit stack. Breadth-first search uses a queue and explores vertices in nondecreasing edge distance from the start. With adjacency lists, both traverse reachable vertices and edges in O(V+E), assuming constant-time visited checks. BFS stores a predecessor when first discovering each vertex. Following predecessors backwards reconstructs a route. DFS finds a route but does not generally minimise its edge count.

BFS minimises edges only when each edge has the same cost. For nonnegative varying weights, Dijkstra repeatedly finalises the vertex with the smallest tentative distance and relaxes outgoing edges. A priority queue supports efficient selection. A direct edge of cost 100 loses to two edges costing 1 each, despite having fewer edges. Negative weights violate Dijkstra's finalisation argument; other algorithms are needed. State the objective before calling a route shortest, and distinguish unreachable from unknown vertices.

Download each script and run it in a terminal with Python 3.11 or later: python m07_tree.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Draw the tree, predict traversal and height, then follow the base case for None.

Download m07_tree.py

"""Recursive traversal with an explicit empty-tree base case."""
def inorder(node):
    if node is None:
        return []
    value, left, right = node
    return inorder(left) + [value] + inorder(right)

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node[1]), height(node[2]))

tree = (4, (2, (1, None, None), (3, None, None)), (6, None, None))
print("inorder:", inorder(tree))
print("height:", height(tree))
assert inorder(tree) == [1, 2, 3, 4, 6]
assert inorder(None) == [] and height(None) == 0

inorder: [1, 2, 3, 4, 6]
height: 3

1. Implement preorder.
2. Make a three-node chain.
3. Explain why concatenating lists repeatedly adds copying cost.

The graph includes cycles and an isolated vertex. BFS records parents at discovery and returns None for an unreachable target.

Download m07_routes.py

"""BFS finds a shortest path measured in edges in an unweighted graph."""
from collections import deque
def route(graph, start, goal):
    if start not in graph or goal not in graph:
        raise KeyError("unknown vertex")
    queue, parent = deque([start]), {start: None}
    while queue:
        vertex = queue.popleft()
        if vertex == goal:
            path = []
            while vertex is not None:
                path.append(vertex); vertex = parent[vertex]
            return path[::-1]
        for neighbour in graph[vertex]:
            if neighbour not in parent:
                parent[neighbour] = vertex; queue.append(neighbour)
    return None

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
print("A to D:", route(graph, "A", "D"))
print("A to E:", route(graph, "A", "E"))
assert route(graph, "A", "D") == ["A", "B", "D"]
assert route(graph, "A", "A") == ["A"]
assert route(graph, "A", "E") is None

A to D: ['A', 'B', 'D']
A to E: None

1. Swap A's neighbour order.
2. Add E to D's neighbours in both directions.
3. Pass an unknown vertex and compare with unreachable E.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• MIT algorithm lectures — Read graph search and shortest paths; distinguish the objectives.

Trace parents for an unreachable and a tied shortest path. Explain the recursive empty case. Module 08 compares design strategies beyond traversal.