These are the notes for Python episode 36, part three of data structures and algorithms. Raju's app menu has categories inside categories, and nested loops can't follow a depth you don't know in advance, so you invent the tree and walk it with depth-first search (DFS), first with recursion and then with your own stack. A level-by-level screen needs breadth-first search (BFS) with a queue. Then Raju's delivery roads loop around, so you invent the graph, fix an endless walk with a visited set, and use BFS to find the route with the fewest stops. Every program below ran for real (Python 3.13.18).
The problem: a menu inside a menu
Menu → Drinks → Hot → Chai. A linked-list node (episode 35) has one next, but a menu branches. The obvious attempt: nested lists and nested loops.
menu = ["Drinks", ["Hot", ["Chai", "Coffee"]], ["Cold", ["Lassi"]]]
for item in menu:
if isinstance(item, list):
for sub in item:
print(" ", sub)
else:
print(item)
Output:
Drinks
Hot
['Chai', 'Coffee']
Cold
['Lassi']
The third level prints as raw lists. Two loops reach two levels; the menu has three, and tomorrow it may have four. You can't type an unknown number of loops. We need a shape that branches, and a walk that goes as deep as the data.
The tree
Real-life picture: a family tree.
| Family tree | Tree term | Meaning |
|---|---|---|
| Dadaji at the top | root | the top node; every node comes from it |
| His children, and theirs | parent / child | each node has one parent (except the root) and any number of children |
| Brothers and sisters | siblings | children of the same parent |
| The youngest, no children yet | leaf | a node with no children |
| Generation 0, 1, 2... | depth / level | steps down from the root (root = 0) |
| The number of generations | height | the depth of the deepest leaf |
| One branch of the family | subtree | a node and everything below it |
A tree is nodes connected parent-to-child, with one root and no loops. A binary tree is a tree where every node has at most two children (left and right). A binary search tree (BST) keeps smaller values on the left and bigger on the right, so a search can throw away half the tree at each step, like binary search (episode 37).
class TreeNode: # a binary tree node
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Raju's menu as a tree: Menu is the root; Drinks and Snacks are its children (depth 1); Hot and Cold are children of Drinks; the dishes (Chai, Coffee, Lassi, Samosa, Vada Pav) are the leaves.
Building the tree and walking it with DFS
class Node:
def __init__(self, name):
self.name = name
self.children = [] # any number of branches
def add(self, *names):
kids = [Node(n) for n in names]
self.children.extend(kids)
return kids
menu = Node("Menu")
drinks, snacks = menu.add("Drinks", "Snacks")
hot, cold = drinks.add("Hot", "Cold")
hot.add("Chai", "Coffee")
cold.add("Lassi")
snacks.add("Samosa", "Vada Pav")
def show(node, depth=0): # DFS: go deep first
print(" " * depth + node.name)
for child in node.children:
show(child, depth + 1)
show(menu)
Output:
Menu
Drinks
Hot
Chai
Coffee
Cold
Lassi
Snacks
Samosa
Vada Pav
show handles one node and calls itself on each child, one level deeper: recursion (episode 15). It works at any depth. The order (Menu, Drinks, Hot, Chai, Coffee, then Cold) goes as deep as possible down one branch before coming back: that's depth-first search (DFS). Printing a node before its children is called pre-order; after them, post-order; for a binary tree, left-node-right is in-order (which visits a BST in sorted order).
Deep trees: RecursionError
class Node:
def __init__(self, name):
self.name = name
self.children = []
def count(node):
return 1 + sum(count(c) for c in node.children)
# a very deep tree: a chain of 5,000 sub-menus
root = Node("level 0")
node = root
for i in range(1, 5000):
child = Node(f"level {i}")
node.children.append(child)
node = child
print(count(root))
Output (last lines):
File "main.py", line 7, in count
return 1 + sum(count(c) for c in node.children)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded
Every call waits on Python's call stack (episode 34). Python stops at about 1,000 waiting calls (sys.getrecursionlimit()), so a runaway recursion can't eat all the memory. Raising the limit with sys.setrecursionlimit is risky; the clean fix is to use your own stack.
DFS with your own stack
class Node:
def __init__(self, name):
self.name = name
self.children = []
root = Node("level 0")
node = root
for i in range(1, 5000):
child = Node(f"level {i}")
node.children.append(child)
node = child
def count(root): # DFS with our own stack
stack, total = [root], 0
while stack:
node = stack.pop() # newest first = go deep
total += 1
stack.extend(node.children)
return total
print(count(root))
Output:
5000
DFS = a stack of places still to visit. pop() takes the newest, so the walk keeps going deeper. (To visit children in their original order, push them reversed: stack.extend(reversed(node.children)).)
BFS: level by level
Raju wants the top level first, then the whole second level, and so on. Visiting nearest first is breadth-first search (BFS), and the only change from DFS is: swap the stack for a queue (deque, episode 34). Oldest first means each level finishes before the next starts.
from collections import deque
menu = {"Menu": ["Drinks", "Snacks"], "Drinks": ["Hot", "Cold"],
"Snacks": ["Samosa", "Vada Pav"], "Hot": ["Chai", "Coffee"],
"Cold": ["Lassi"]}
def bfs(start):
queue = deque([(start, 0)])
while queue:
name, level = queue.popleft() # oldest first = level by level
print(f"level {level}: {name}")
for child in menu.get(name, []):
queue.append((child, level + 1))
bfs("Menu")
Output:
level 0: Menu
level 1: Drinks
level 1: Snacks
level 2: Hot
level 2: Cold
level 2: Samosa
level 2: Vada Pav
level 3: Chai
level 3: Coffee
level 3: Lassi
Here the tree is stored as a dictionary: each name maps to a list of its children's names. menu.get(name, []) returns an empty list for leaves.
Graphs
Raju delivers from his kitchen to areas joined by roads. A road map is not a tree: Kitchen → Andheri → Juhu → Bandra → Kitchen comes back to where it started.
| City map | Graph term | Meaning |
|---|---|---|
| An area | node (vertex) | a thing |
| A road between two areas | edge | a connection |
| Two-way roads | undirected graph | edges work both ways |
| One-way streets | directed graph | edges have a direction (A → B) |
| Road lengths in km | weighted graph | edges have a cost |
| Areas next to an area | neighbours | nodes joined by one edge |
| A round trip back to the start | cycle | a path that returns to its first node |
A tree is a graph with no cycles (and connected). The usual way to store a graph in Python is an adjacency list: a dict mapping each node to a list of its neighbours. (An adjacency matrix is an n×n table of 0/1: simple, but n² memory.)
roads = {
"Kitchen": ["Andheri", "Bandra"],
"Andheri": ["Kitchen", "Juhu"],
"Bandra": ["Kitchen", "Juhu", "Dadar"],
"Juhu": ["Andheri", "Bandra"],
"Dadar": ["Bandra"],
}
The tree walk on a graph: going round in circles
def visit(area): # the tree walk, on a map
print("visit", area)
for nxt in roads[area]:
visit(nxt)
visit("Kitchen")
Output (start and end):
visit Kitchen
visit Andheri
visit Kitchen
visit Andheri
...
RecursionError: maximum recursion depth exceeded
Kitchen leads to Andheri, and Andheri leads straight back to Kitchen. In a tree you can never return to a node; in a graph, cycles bring you back forever. (With an explicit stack and no visited set, the loop would never end at all.)
The fix: a visited set
def dfs(area, visited):
visited.add(area) # mark it: never again
print("visit", area)
for nxt in roads[area]:
if nxt not in visited:
dfs(nxt, visited)
dfs("Kitchen", set())
Output:
visit Kitchen
visit Andheri
visit Juhu
visit Bandra
visit Dadar
Each area exactly once. Use a set (O(1) checks, thanks to hashing, episode 35), not a list. Every node and every edge is handled once, so DFS and BFS cost O(V + E): V = number of vertices (nodes), E = number of edges.
BFS finds the fewest stops
BFS spreads out from the start like a ripple: first everything 1 road away, then 2, then 3. So the first time BFS reaches a node is by the fewest edges. Remember where each node was reached from, then walk backwards from the goal.
from collections import deque
roads = {
"Kitchen": ["Andheri", "Bandra"],
"Andheri": ["Kitchen", "Juhu"],
"Bandra": ["Kitchen", "Juhu", "Dadar"],
"Juhu": ["Andheri", "Bandra", "Worli"],
"Dadar": ["Bandra", "Worli"],
"Worli": ["Juhu", "Dadar"],
}
def fewest_stops(start, goal):
came_from = {start: None} # visited + how we got here
queue = deque([start])
while queue:
area = queue.popleft()
if area == goal:
break
for nxt in roads[area]:
if nxt not in came_from:
came_from[nxt] = area
queue.append(nxt)
path, area = [], goal
while area is not None: # walk back to the start
path.append(area)
area = came_from[area]
return path[::-1]
print(fewest_stops("Kitchen", "Worli"))
print(fewest_stops("Kitchen", "Dadar"))
Output:
['Kitchen', 'Andheri', 'Juhu', 'Worli']
['Kitchen', 'Bandra', 'Dadar']
came_from is both the visited set and the route. Mark a node as visited when you add it to the queue, not when you pop it, or it can be added many times. If the goal can't be reached, came_from[goal] would raise KeyError; the mini project handles that.
BFS counts edges. If roads have different lengths, use Dijkstra's algorithm, which swaps the queue for a priority queue (heapq).
BFS or DFS?
| DFS | BFS | |
|---|---|---|
| Structure | stack (or recursion) | queue (deque) |
| Order | deep first, one branch at a time | nearest first, level by level |
| Good for | visiting everything, folders, puzzles/backtracking, cycle checks, topological order | levels, fewest stops, friends of friends, nearest X |
| Graphs | needs a visited set | needs a visited set |
| Time | O(V + E) | O(V + E) |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
one for loop per level |
the 3rd level prints as a raw list | the depth isn't known | recursion or a stack |
| recursive DFS on a 5,000-deep tree | RecursionError: maximum recursion depth exceeded |
Python stops at ~1,000 calls | DFS with your own stack |
a graph walk without visited |
RecursionError or an endless loop |
cycles bring you back | visited = set() |
visited as a list |
slow on big graphs | x in list is O(n) |
a set or dict |
| marking visited when popping (BFS) | nodes queued many times | added before being marked | mark when appending |
| DFS for the fewest stops | a long route | DFS goes deep, not near | BFS with a deque |
| one-way edges stored for a two-way road | some areas "unreachable" | the edge only goes one way | add both directions |
Mini project: Raju's delivery route planner
roads.txt: one road per line, likeKitchen,Andheri.- Build the adjacency list in both directions.
- BFS from Kitchen: the number of stops to every area.
route(area): the path with the fewest stops.- DFS: which areas can't be reached at all?
- An area with no route prints a clear message, no crash.
roads.txt:
Kitchen,Andheri
Kitchen,Bandra
Andheri,Juhu
Bandra,Juhu
Bandra,Dadar
Juhu,Worli
Dadar,Worli
Colaba,Fort
Solution
from collections import deque
def load_roads(path):
roads = {}
with open(path) as f:
for line in f:
line = line.strip()
if not line:
continue
a, b = line.split(",")
roads.setdefault(a, []).append(b) # both directions
roads.setdefault(b, []).append(a)
return roads
def bfs(roads, start):
came_from, stops = {start: None}, {start: 0}
queue = deque([start])
while queue:
area = queue.popleft()
for nxt in roads[area]:
if nxt not in came_from:
came_from[nxt] = area
stops[nxt] = stops[area] + 1
queue.append(nxt)
return came_from, stops
def route(came_from, goal):
if goal not in came_from:
return None
path = []
while goal is not None:
path.append(goal)
goal = came_from[goal]
return path[::-1]
def reachable(roads, start): # DFS with a stack
seen, stack = {start}, [start]
while stack:
area = stack.pop()
for nxt in roads[area]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return seen
roads = load_roads("roads.txt")
came_from, stops = bfs(roads, "Kitchen")
for area, n in sorted(stops.items(), key=lambda kv: kv[1]):
print(f"{area:<8} {n} stops")
for goal in ["Worli", "Fort"]:
path = route(came_from, goal)
print(goal, "->", " -> ".join(path) if path else "no route from the kitchen")
print("unreachable:", sorted(set(roads) - reachable(roads, "Kitchen")))
Output:
Kitchen 0 stops
Andheri 1 stops
Bandra 1 stops
Juhu 2 stops
Dadar 2 stops
Worli 3 stops
Worli -> Kitchen -> Andheri -> Juhu -> Worli
Fort -> no route from the kitchen
unreachable: ['Colaba', 'Fort']
dict.setdefault(key, []) returns the list for key, creating an empty one first if needed.
Practice
1. Find the depth (height) of the menu tree, and count its leaves.
Solution
class Node:
def __init__(self, name):
self.name, self.children = name, []
def depth(node):
if not node.children:
return 0
return 1 + max(depth(c) for c in node.children)
def leaves(node):
if not node.children:
return 1
return sum(leaves(c) for c in node.children)
menu = Node("Menu")
drinks, snacks = Node("Drinks"), Node("Snacks")
hot, cold = Node("Hot"), Node("Cold")
menu.children = [drinks, snacks]
drinks.children = [hot, cold]
hot.children = [Node("Chai"), Node("Coffee")]
cold.children = [Node("Lassi")]
snacks.children = [Node("Samosa"), Node("Vada Pav")]
print("depth:", depth(menu), "| leaves:", leaves(menu))
Output: depth: 3 | leaves: 5
2. Does an undirected graph have a cycle? Use DFS: meeting an already-visited node that isn't the one you just came from means a cycle.
Solution
def has_cycle(graph): # undirected graph
seen = set()
def dfs(node, parent):
seen.add(node)
for nxt in graph[node]:
if nxt not in seen:
if dfs(nxt, node):
return True
elif nxt != parent: # seen, and not where we came from
return True
return False
return any(dfs(n, None) for n in graph if n not in seen)
tree = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
loop = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
print(has_cycle(tree), has_cycle(loop))
Output: False True
3. BFS vs DFS order. For {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []} from A, write both orders.
Solution
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
seen, q, order = {"A"}, deque(["A"]), []
while q:
n = q.popleft(); order.append(n)
for m in graph[n]:
if m not in seen:
seen.add(m); q.append(m)
print(" ".join(order))
seen, order = set(), []
def dfs(n):
seen.add(n); order.append(n)
for m in graph[n]:
if m not in seen: dfs(m)
dfs("A"); print(" ".join(order))
Output:
A B C D E
A B D C E
Quick quiz
graph = {"A": ["B", "C"], "B": ["D"],
"C": ["D", "E"], "D": [], "E": []}
# BFS from "A", children in list order,
# with a visited set
Options: A B D C E, A C E D B, A B C D E, A B C E D
Answer
A B C D E. Level 0 is A; level 1 is B and C; level 2 is D (reached from B first) and E. A B D C E is the DFS order.
Interview questions
- Difference between BFS and DFS? BFS uses a queue and visits nearest nodes first (level order); DFS uses a stack or recursion and goes deep first. Both are O(V + E).
- Why does BFS give the shortest path in an unweighted graph? It visits nodes in order of their distance in edges, so the first time it reaches a node is by the fewest edges.
- Why do graph traversals need a visited set but tree traversals often don't? Trees have no cycles and each node has one parent, so you never revisit a node; graphs can have cycles and many paths to the same node.
- Adjacency list vs adjacency matrix? A list uses O(V + E) memory and is best for sparse graphs; a matrix uses O(V²) memory but answers "is there an edge u–v?" in O(1).
- How do you avoid RecursionError in DFS? Use an explicit stack (a list) instead of recursion.
- What is a binary search tree? A binary tree where every left subtree has smaller values and every right subtree bigger ones; search, insert and delete are O(log n) when balanced, O(n) when it degenerates into a chain.
- Shortest path with weighted edges? Dijkstra's algorithm with a priority queue (non-negative weights).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Tree | Nodes connected parent-to-child, one root, no cycles | Raju's menu |
| Root | The top node of a tree | Menu |
| Parent / child | A node and the nodes directly below it | Drinks → Hot |
| Siblings | Children of the same parent | Hot and Cold |
| Leaf | A node with no children | Chai |
| Depth / level | Steps down from the root (root = 0) | Hot is at depth 2 |
| Height | The depth of the deepest leaf | the menu's height is 3 |
| Subtree | A node and everything below it | the Drinks subtree |
| Binary tree | Every node has at most two children | left, right |
| Binary search tree (BST) | Smaller values left, bigger right | fast sorted search |
| Traversal | Visiting every node in some order | DFS, BFS |
| DFS | Depth-first search: go deep down one branch first | stack / recursion |
| BFS | Breadth-first search: nearest first, level by level | queue (deque) |
| Pre-order / post-order / in-order | Visit a node before / after / between its children | printing the menu is pre-order |
| Call stack | The stack of function calls waiting to return | recursion |
RecursionError |
Too many nested calls (about 1,000 by default) | a 5,000-deep tree |
| Graph | Nodes joined by edges, cycles allowed | a city road map |
| Node / vertex | One thing in a graph | Andheri |
| Edge | A connection between two nodes | a road |
| Undirected / directed | Edges work both ways / one way | two-way roads / one-way streets |
| Weighted graph | Edges have a cost | road length in km |
| Neighbours | Nodes joined to a node by one edge | Bandra's neighbours |
| Cycle | A path that returns to its start | Kitchen → Andheri → Juhu → Bandra → Kitchen |
| Adjacency list | Each node maps to a list of its neighbours | roads = {"Kitchen": [...]} |
| Adjacency matrix | An n×n table: 1 where there's an edge | m[u][v] = 1 |
| Visited set | The nodes already seen, so none is processed twice | visited = set() |
| O(V + E) | Time proportional to nodes plus edges | BFS and DFS |
| Shortest path (fewest stops) | The route with the fewest edges | BFS with came_from |
| Dijkstra's algorithm | Shortest path when edges have different costs | uses heapq |
Summary
- A tree branches from a root to leaves; store children in a list (or a dict of lists).
- DFS goes deep first, with recursion or your own stack; deep recursion gives
RecursionError, so use a stack for deep data. - BFS goes level by level with a queue (
deque). - A graph is nodes and edges, stored as an adjacency list; cycles need a visited set.
- BFS finds the fewest stops; record
came_fromand walk back to get the route. Both BFS and DFS are O(V + E). - Next episode: sorting, binary search and two pointers.