SyntaxPilot
Courses/Python/Lesson 36
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python · Lesson 36 of 40

DSA 3: trees and graphs, BFS and DFS

queued

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

  1. roads.txt: one road per line, like Kitchen,Andheri.
  2. Build the adjacency list in both directions.
  3. BFS from Kitchen: the number of stops to every area.
  4. route(area): the path with the fewest stops.
  5. DFS: which areas can't be reached at all?
  6. 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

  1. 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).
  2. 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.
  3. 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.
  4. 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).
  5. How do you avoid RecursionError in DFS? Use an explicit stack (a list) instead of recursion.
  6. 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.
  7. 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_from and walk back to get the route. Both BFS and DFS are O(V + E).
  • Next episode: sorting, binary search and two pointers.