Measure efficiency with Big-O, then use searching, sorting, hash maps, stacks, linked lists, trees, graphs and dynamic programming in Python.

Data Structures & Algorithms

## Why it matters

Some problems are naturally made of smaller copies of themselves: a folder contains folders, a tree contains subtrees, a nested JSON document contains nested documents, and merge sort sorts two halves. **Recursion**, a function that calls itself on a smaller piece of the problem, is the cleanest way to write code for these shapes. You need it for trees and graphs in the next two lessons and for dynamic programming later.

## The core idea

Every recursive function has two parts:

1. **Base case**: an input small enough to answer directly, with no further calls.
2. **Recursive case**: break the problem into a smaller version, call the function on it, and use the result.

The recursive case must always move **toward** the base case, or the function never stops.

```python
def factorial(n):
    if n <= 1:                     # base case: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)    # smaller problem: n - 1
```

## How it runs: the call stack

Each call gets its own copy of its local variables and waits on the **call stack** until the call it made returns.

```text
factorial(4)
  4 * factorial(3)
        3 * factorial(2)
              2 * factorial(1)
                    return 1         <- base case
              return 2 * 1 = 2
        return 3 * 2 = 6
  return 4 * 6 = 24
```

The calls go down until the base case, then the answers come back up. If there is no base case, Python stops you with `RecursionError: maximum recursion depth exceeded` (the default limit is about 1,000 calls deep).

## Worked example 1: sum of digits

The digits of `482` add up to `4 + 8 + 2 = 14`. The last digit is `n % 10` and the rest is `n // 10`:

```python
def sum_digits(n):
    if n < 10:                              # one digit: answer directly
        return n
    return n % 10 + sum_digits(n // 10)

sum_digits(482)   # 2 + sum_digits(48) = 2 + 8 + sum_digits(4) = 14
```

## Worked example 2: flattening nested lists

`[1, [2, [3, 4]], 5]` should become `[1, 2, 3, 4, 5]`. You do not know how deep the nesting goes, which is exactly when recursion beats loops.

```python
def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))    # a smaller problem of the same shape
        else:
            result.append(item)
    return result
```

Here the base case is implicit: a list with no inner lists makes no further calls, and an empty list returns `[]` straight away.

## Worked example 3: counting paths

How many ways can you climb `n` stairs taking 1 or 2 steps at a time? The last move was either a 1-step (from stair `n - 1`) or a 2-step (from stair `n - 2`), so:

```python
def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)
```

It is correct but slow: `climb(40)` repeats the same sub-calls millions of times. You will fix that with memoisation in the dynamic programming lesson.

## How to write a recursive function

1. **Write the signature and say in words what it returns.** "`sum_digits(n)` returns the sum of the digits of n."
2. **Find the smallest inputs** and answer them directly (0, 1, empty list, a leaf node).
3. **Assume the function already works on a smaller input** (this is the "leap of faith") and write how to use that answer.
4. **Check that every call gets smaller.** `n - 1`, `n // 10`, a sublist, a child node.
5. **Test the base cases first**, then a slightly bigger input by tracing by hand.

## Recursion or a loop?

Anything recursive can be written with a loop and an explicit stack, and Python does not optimise deep recursion. Use recursion when the data is nested or tree-shaped and the depth is modest (hundreds, not hundreds of thousands). Use a loop for simple counting down a long sequence.

## Common mistakes

- **No base case, or one that is never reached**, for example `factorial(-1)` with a base case of `n == 1` only. Use `n <= 1`.
- **Forgetting `return`.** `factorial(n - 1)` on its own line computes the answer and throws it away.
- **Not making the problem smaller**, such as calling `f(n)` from inside `f(n)`.
- **Sharing a mutable default** like `def f(items, out=[])`. The same list is reused between calls; build and return a new list instead.

## Quick recap

- Recursion = base case + a call on a smaller input.
- Calls stack up until the base case, then results return in reverse order.
- Trust the smaller call, combine its answer, and test the base cases first.
- Python's depth limit is about 1,000; use loops for very long chains.

## Try it

In the **Do** tab, write `factorial`, `sum_digits` and `flatten` recursively. The checks include the base cases (0, a single digit, an empty list) and deep nesting.


Write functions that call themselves on a smaller input, with a base case that stops them.

Recursion

Recursion - CS50 Shorts

What on Earth is Recursion? - Computerphile

## Why it matters

Trees model anything hierarchical: folders on disk, the HTML elements of a web page (the DOM), an organisation chart, a decision tree in machine learning, a parsed expression in a compiler. Database indexes use balanced trees (B-trees) so lookups stay fast as tables grow. Once you can walk a tree recursively, all of these become approachable.

## Vocabulary

A **tree** is made of **nodes** connected by edges, with one **root** at the top. Each node can have **children**; a node with no children is a **leaf**. In a **binary tree**, each node has at most two children, called `left` and `right`. The **height** is the number of nodes on the longest path from the root down to a leaf (an empty tree has height 0).

```python
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

#        8
#      /   \
#     3     10
#    / \      \
#   1   6      14
root = TreeNode(8,
                TreeNode(3, TreeNode(1), TreeNode(6)),
                TreeNode(10, None, TreeNode(14)))
```

## Traversals: visiting every node

Every node's `left` and `right` are themselves trees (or `None`), so tree functions are naturally recursive. The base case is the empty tree, `None`. The three depth-first orders differ only in **when** you visit the current node:

| order | visit | result for the tree above |
|---|---|---|
| pre-order | node, left, right | 8, 3, 1, 6, 10, 14 |
| in-order | left, node, right | 1, 3, 6, 8, 10, 14 |
| post-order | left, right, node | 1, 6, 3, 14, 10, 8 |

```python
def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)
```

When do you use which? **Pre-order** copies or prints a structure top-down (like listing a folder before its contents). **Post-order** handles children before parents (like adding up folder sizes, or deleting a tree). **In-order** gives sorted output for a binary search tree.

A fourth order, **level-order** (breadth-first), visits row by row: 8, then 3 and 10, then 1, 6, 14. It uses a queue instead of recursion; you will meet it in the next lesson on BFS.

## Height

The same pattern answers many questions. The height of a tree is one (for this node) plus the taller of its two subtrees:

```python
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))
```

The example tree has height 3.

## Binary search trees (BSTs)

A **BST** adds one rule: for every node, all values in its left subtree are **smaller** and all values in its right subtree are **larger**. The tree above is a BST. That rule means you can search like binary search: compare with the node and go left or right, discarding a whole subtree each time.

Inserting follows the same path until it finds an empty spot:

```python
def bst_insert(node, value):
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = bst_insert(node.left, value)
    elif value > node.value:
        node.right = bst_insert(node.right, value)
    return node          # duplicates are ignored

root = None
for v in [8, 3, 10, 1, 6, 14]:
    root = bst_insert(root, v)
inorder(root)        # [1, 3, 6, 8, 10, 14]
```

The function returns the (possibly new) root of each subtree, so the empty-tree case and the "attach a new child" case are the same line.

**Cost.** Search and insert take time proportional to the height. A **balanced** BST with `n` nodes has height about `log n`, so operations are **O(log n)**. But inserting values that are already sorted (1, 2, 3, 4, ...) makes every node a right child: the tree becomes a linked list of height `n`, and operations become **O(n)**. Self-balancing trees (red-black, AVL, B-trees) fix this, and they are what real libraries and databases use.

## Common mistakes

- **Forgetting the `None` base case**, which causes `AttributeError: 'NoneType' object has no attribute 'left'`.
- **Mixing up the orders.** Say it out loud: in-order means the node goes **in** the middle.
- **Not reassigning the result of insert** (`node.left = bst_insert(node.left, value)`), so new nodes are created but never attached.
- **Assuming a BST is always fast.** Sorted input makes it a list.

## Quick recap

- Binary tree: nodes with `left` and `right`; `None` is the empty tree and the base case.
- Pre-order (node first), in-order (node in the middle), post-order (node last).
- BST rule: left smaller, right larger; in-order gives sorted values.
- BST operations cost O(height): O(log n) if balanced, O(n) if not.

## Try it

In the **Do** tab, write `inorder`, `preorder`, `height` and `bst_insert`, then check that in-order on a BST you built gives sorted values.


Represent a binary tree with nodes, traverse it in pre-, in- and post-order, and insert into a binary search tree.

Trees and BSTs

Binary tree traversal - breadth-first and depth-first strategies

In-order tree traversal in 3 minutes

## Why it matters

A **graph** is a set of things (**nodes** or vertices) and connections between them (**edges**). Road maps, social networks, web links, package dependencies, network routers, molecules and game levels are all graphs. Two search strategies, **breadth-first search (BFS)** and **depth-first search (DFS)**, answer most beginner graph questions: Can I get from A to B? What is the shortest route? Which parts are connected? Trees are just graphs with no cycles, so you already know half of this.

## Representing a graph

The most common representation is an **adjacency list**: a dict from each node to the list of its neighbours.

```python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
```

This graph is **undirected** (if A connects to B, B lists A). In a **directed** graph, such as "package X depends on Y", edges go one way. A grid is a graph too: each open cell is a node, and its neighbours are the open cells up, down, left and right.

Unlike trees, graphs can have **cycles** (A -> B -> D -> C -> A). Any graph search must remember which nodes it has already **visited**, or it will loop forever.

## Depth-first search (DFS)

DFS goes as deep as it can along one path, then backs up and tries the next. It is naturally recursive (or uses a stack).

```python
def has_path(graph, start, goal, visited=None):
    if visited is None:
        visited = set()
    if start == goal:
        return True
    visited.add(start)
    for neighbour in graph.get(start, []):
        if neighbour not in visited:
            if has_path(graph, neighbour, goal, visited):
                return True
    return False

has_path(graph, "A", "E")   # True
```

DFS is good for "is there any path?", finding connected groups, detecting cycles and ordering dependencies. It does **not** guarantee the shortest path. (Note `visited=None` and a new set inside: a mutable default like `visited=set()` would be shared between calls.)

## Breadth-first search (BFS)

BFS explores in rings: first every node one step away, then every node two steps away, and so on. It uses a **queue** (first in, first out). Because it reaches nodes in order of distance, the **first time BFS reaches a node is by a shortest path** (counting edges).

```python
from collections import deque

def distances_from(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph.get(node, []):
            if neighbour not in dist:          # dist doubles as "visited"
                dist[neighbour] = dist[node] + 1
                queue.append(neighbour)
    return dist

distances_from(graph, "A")   # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}
```

Mark a node as seen **when you add it to the queue**, not when you take it out, so it is never queued twice.

## Worked example: shortest path in a grid

A maze is a list of strings, `.` for open and `#` for a wall. Find the fewest moves from the top-left to the bottom-right, moving up, down, left or right.

```python
from collections import deque

def shortest_path_length(grid):
    if not grid or not grid[0]:
        return -1
    rows, cols = len(grid), len(grid[0])
    goal = (rows - 1, cols - 1)
    if grid[0][0] == "#" or grid[goal[0]][goal[1]] == "#":
        return -1
    queue = deque([(0, 0, 0)])          # row, col, steps so far
    seen = {(0, 0)}
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == goal:
            return steps
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    return -1

maze = ["..#",
        ".##",
        "..."]
shortest_path_length(maze)   # 4: down, down, right, right
```

The pieces you will reuse in every grid problem: a **bounds check**, a **wall check**, a **seen set**, and a list of four **directions**. A one-cell open grid returns 0; a blocked start or goal returns -1.

**Cost.** BFS and DFS each visit every node and edge at most once: **O(V + E)** for V nodes and E edges. A grid with R rows and C columns is O(R x C).

## BFS or DFS?

| question | use |
|---|---|
| Fewest steps / shortest path (unweighted) | BFS |
| Is there any path? Which nodes are connected? | either; DFS is often shorter to write |
| Explore every option, backtrack (puzzles) | DFS |
| Shortest path with different edge costs (road distances) | Dijkstra's algorithm, a later topic |

## Common mistakes

- **No visited set**, so cycles cause infinite loops.
- **Marking visited too late in BFS**, so the same cell is queued many times.
- **Using DFS for shortest paths.** It finds a path, not necessarily the shortest.
- **Off-by-one bounds checks** (`<=` instead of `<`) that crash with `IndexError`.
- **A mutable default `visited=set()`** shared between separate calls.

## Quick recap

- Graphs are nodes plus edges; store them as an adjacency list (dict of lists).
- DFS goes deep (recursion or a stack); BFS goes in rings (a deque).
- BFS finds the shortest path in an unweighted graph or grid.
- Always track visited nodes. Cost is O(V + E).

## Try it

In the **Do** tab, write `has_path` with DFS and `shortest_path_length` with BFS on a grid. The checks include an empty grid, a single cell, blocked starts and unreachable goals.


Represent a graph as an adjacency list, explore it with depth-first search, and find shortest paths in a grid with breadth-first search.

Graphs, BFS, and DFS

Breadth-first search in 4 minutes

Depth-first search in 4 minutes

Write recursive functions, traverse binary trees and binary search trees, and explore graphs and grids with depth-first and breadth-first search.