Trees and Graphs

TL;DR

You'll know how to traverse any tree or graph using DFS and BFS, when to pick recursion versus an explicit stack, and how to detect cycles or find shortest paths. You'll see the four traversal patterns that solve 80% of Leetcode tree/graph problems. You'll also know the classic bugs that break submissions on edge cases.

1. The Mental Model

A tree is just a graph with no cycles and one path between any two nodes. Every traversal problem is really a question: "do I need to go deep first, or spread out level by level?" DFS answers questions about paths and structure; BFS answers questions about distance and layers. If the question mentions "shortest" or "level," think BFS; if it mentions "path" or "all combinations," think DFS.

2. The Core Material

2.1 DFS — recursion, two stacks, and the three orders

Photo by Shawn Stutzman on Pexels

DFS goes as deep as possible before backtracking. On trees, it comes in three flavors depending on when you process the current node relative to its children.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):   # root, left, right — good for copying/serializing
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):    # left, root, right — gives sorted order on a BST
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):  # left, right, root — good for deletion/aggregation
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

Recursion is clean but costs call-stack space — O(h) where h is tree height. On a skewed tree, h = n, and Python's default recursion limit (1000) will blow up. The iterative version with an explicit stack avoids that:

def preorder_iterative(root):
    if not root:
        return []
    stack, out = [root], []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:   # push right first so left pops first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

On graphs, DFS needs a visited set because cycles exist. Forgetting it is the single most common bug in this topic.

def dfs_graph(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                stack.append(nxt)
    return order

2.2 BFS — the shortest-path workhorse

BFS explores level by level using a queue (collections.deque, never a plain list — popping from the front of a list is O(n)). It's the only correct tool when you need shortest path in an unweighted graph, because it guarantees you visit nodes in increasing distance order.

from collections import deque

def bfs_shortest_path(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for nxt in graph[node]:
            if nxt == target:
                return dist + 1
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

Key detail: mark nodes visited when you enqueue them, not when you dequeue them. If you mark on dequeue, the same node can be pushed multiple times by different neighbors before it's processed, wasting work and in dense graphs causing real slowdowns.

2.3 Graph representations and cycle detection

Photo by AlphaTradeZone on Pexels

Most Leetcode graph problems give you an edge list; you convert it to an adjacency list first — this is non-negotiable for anything beyond trivial size.

from collections import defaultdict

def build_graph(n, edges, directed=False):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

Cycle detection differs for directed vs undirected graphs — this trips people up constantly:

• Undirected graph: a cycle exists if, during DFS, you reach an already-visited node that is not the immediate parent.
• Directed graph: you need three states (white/unvisited, gray/in current recursion path, black/fully done). A cycle exists if you ever hit a gray node — that means you've looped back into your own current path.

def has_cycle_directed(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True
            if color[nxt] == WHITE and dfs(nxt):
                return True
        color[node] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(n))

This same gray/black idea underlies topological sort (Kahn's algorithm using in-degrees + BFS, or DFS with a postorder reversal) — if you can detect a cycle this way, you already understand why topological sort fails on cyclic graphs: there's no valid linear order.

flowchart TD
    A["Problem mentions tree or graph"] --> B{"Need shortest path / levels?"}
    B -->|Yes| C["BFS with deque"]
    B -->|No| D{"Need all paths / combinations / backtracking?"}
    D -->|Yes| E["DFS, often with backtracking"]
    D -->|No| F{"Directed graph with dependencies?"}
    F -->|Yes| G["Topological sort (Kahn's or DFS postorder)"]
    F -->|No| H{"Need connectivity / cycle check?"}
    H -->|Yes| I["DFS or Union-Find"]

3. Worked Example

Problem: "Number of Islands" — given a 2D grid of '1's (land) and '0's (water), count connected land regions (4-directionally connected).

This is a graph problem in disguise: each cell is a node, edges connect to its 4 neighbors, and you need connected components — a classic DFS-from-each-unvisited-node pattern.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = cr + dr, cc + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and (nr, nc) not in visited
                        and grid[nr][nc] == '1'):
                    visited.add((nr, nc))
                    stack.append((nr, nc))

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                visited.add((r, c))
                count += 1
                dfs(r, c)
    return count

Trace through grid = [["1","1","0"],["0","1","0"],["0","0","1"]]:

• (0,0) is land, unvisited → new island #1. DFS floods (0,0) → (0,1) → (1,1). All three marked visited.
• (0,2) is water, skip.
• (2,2) is land, unvisited → new island #2. DFS finds no connected land neighbors.

Result: count = 2. Time complexity is O(rows * cols) since every cell is visited at most once; space is O(rows * cols) for the visited set in the worst case (all land, iterative stack depth up to grid size).

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Always build an adjacency list (defaultdict(list)) from edge lists before traversing — don't scan the edge list repeatedly inside your loop.
• Use collections.deque for BFS queues, never list.pop(0).
• Mark nodes visited at enqueue/push time for BFS to avoid duplicate queue entries; for DFS with recursion, mark at the start of the call.
• For very deep trees, prefer the iterative stack-based traversal over recursion to dodge RecursionError.
• When the grid/graph nodes don't have natural IDs (e.g. grid coordinates), use tuples (r, c) as dictionary/set keys — they're hashable and readable.
• For "shortest path with weights," reach for Dijkstra (heapq) instead of BFS — BFS only guarantees shortest path when all edges weigh the same.
• Use Union-Find (disjoint set with path compression and union by rank) instead of repeated DFS when you need many "are these connected?" queries — it's near O(1) amortized per query versus O(n) per DFS.

4.2 Common Bugs & Anti-Patterns

Bug 1 — forgetting visited on a graph (infinite loop on cycles):

# BAD
def dfs(graph, node):
    print(node)
    for nxt in graph[node]:
        dfs(graph, nxt)   # loops forever if graph has a cycle

# FIXED
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)

Bug 2 — mutable default argument reused across calls:

# BAD — visited persists across separate top-level calls!
def dfs(node, visited=set()):
    ...

# FIXED — create a fresh set each call
def dfs(node, visited=None):
    if visited is None:
        visited = set()
    ...

Bug 3 — marking visited on dequeue instead of enqueue in BFS:

# BAD — same node can be queued many times
while queue:
    node = queue.popleft()
    if node in visited:
        continue
    visited.add(node)
    for nxt in graph[node]:
        queue.append(nxt)

# FIXED — check and mark before pushing
visited = {start}
queue = deque([start])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in visited:
            visited.add(nxt)
            queue.append(nxt)

Bug 4 — treating a directed graph's cycle check like an undirected one:

# BAD — this only checks "visited," which falsely flags diamonds
# (A -> B, A -> C, B -> D, C -> D) as cycles in a directed graph
def has_cycle(graph, node, visited):
    if node in visited:
        return True
    visited.add(node)
    return any(has_cycle(graph, nxt, visited) for nxt in graph[node])

# FIXED — use three-color (white/gray/black) states, shown in 2.3

4.3 When to Use What

5. Now Try It

Write a function course_order(num_courses, prerequisites) that returns a valid order to take num_courses courses given a list of [course, prereq] pairs, or an empty list if it's impossible (cycle exists). Use Kahn's algorithm: build an adjacency list and in-degree array, start a BFS queue with all in-degree-0 nodes, and pop them off, decrementing neighbors' in-degrees. Test it on num_courses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] and on a version with an added edge [0,3] that creates a cycle.

Success looks like: your function returns a valid 4-element order (e.g. [0,1,2,3] or [0,2,1,3]) for the first case, and returns [] for the cyclic case.