DSA · Lesson 9 of 9

Trees & graphs: BFS and DFS

Traversing trees and graphs, shortest paths in unweighted graphs.

A tree is a hierarchy of nodes with one root and no cycles (folders, org charts, the HTML DOM). A binary search tree keeps smaller values on the left and larger on the right.

A graph is nodes connected by edges — cities and roads, people and connections. Store it as an adjacency list: a dict mapping each node to its neighbours.

DFS (depth-first) goes deep before wide — recursion or a stack. Good for exploring all paths, detecting cycles, counting connected parts.
BFS (breadth-first) visits level by level with a queue — gives the shortest path in an unweighted graph.

Always track visited nodes in a graph to avoid infinite loops.

Try it yourself

Code editor

from collections import deque

# Binary tree as nested tuples: (value, left, right)
tree = (8, (3, (1, None, None), (6, None, None)), (10, None, (14, None, None)))

def inorder(node):                      # DFS: left, root, right
    if not node:
        return []
    val, left, right = node
    return inorder(left) + [val] + inorder(right)

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

roads = {
    "Kochi": ["Thrissur", "Alappuzha"],
    "Thrissur": ["Kochi", "Palakkad", "Kozhikode"],
    "Alappuzha": ["Kochi", "Kollam"],
    "Kollam": ["Alappuzha", "Thiruvananthapuram"],
    "Palakkad": ["Thrissur"],
    "Kozhikode": ["Thrissur", "Kannur"],
    "Kannur": ["Kozhikode"],
    "Thiruvananthapuram": ["Kollam"],
}

def shortest_path(graph, start, goal):  # BFS
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        if path[-1] == goal:
            return path
        for nxt in graph[path[-1]]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(path + [nxt])
    return None

print(inorder(tree), "height:", height(tree))
print(" -> ".join(shortest_path(roads, "Kannur", "Thiruvananthapuram")))

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Adjacency list = dict of neighbours.
BFS + queue = shortest path (unweighted).
DFS + recursion/stack = explore deeply; track visited.

Quick check

Which traversal finds the shortest path in an unweighted graph?

DFS BFS Inorder Random walk

Practice task

Write count_islands(grid) that counts groups of connected 1s (up/down/left/right) in a 2-D list using DFS.

Interview corner

Why does inorder traversal of a BST give sorted output?

BST rules put smaller keys in the left subtree and larger in the right, so visiting left, node, right outputs keys in ascending order.

BFS vs DFS memory use?

BFS stores a whole frontier level (can be wide); DFS stores the current path (can be deep). Choose based on the graph's shape and what you need.