Skip to content
Hello Python
4/7

Trees & Graphs

Topic 4 of 7, with 3 concept checks. BFS, DFS, and when to use each

Traverse connected state with an explicit frontier

Connected state

Choose a stack, queue, or recursive frame for the frontier, mark states at the correct time, and separate the graph representation from the traversal invariant.

Core lesson 01

Use BFS for shortest path in an unweighted graph, or level-by-level processing; use DFS for exploring full paths, cycle detection, or when 'shortest' isn't the goal.

BFS visits all nodes at distance 1, then distance 2, then distance 3, using a queue - the first time it reaches a target node is guaranteed to be via the shortest path (unweighted graph). DFS commits to one path as deep as possible before backtracking, using a stack (explicit or recursive) - better suited for exhaustive exploration where 'shortest' isn't the goal.

Python example
from collections import deque

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

What to remember

When should you use BFS instead of DFS?

Common footguns

  • Using DFS to find 'shortest path' in an unweighted graph - DFS finds A path, not necessarily the shortest one, unless you explore every path and compare.

Core lesson 02

Preorder: root, left, right (good for copying/serializing). Inorder: left, root, right (sorted output for a BST). Postorder: left, right, root (good when children's results are needed first).

All three are DFS, differing only in when the current node's value is used relative to recursing into its children. Inorder traversal of a valid binary search tree always yields values in sorted order (a frequently-tested fact), while postorder is the natural fit for anything requiring children's results before the parent's (subtree heights, safe bottom-up deletion).

Python example
def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.val)     # visit AFTER left, BEFORE right
    inorder(node.right, result)

# for a valid BST, `result` ends up sorted

What to remember

What's the difference between preorder, inorder, and postorder tree traversal, and when does each matter?

Common footguns

  • Assuming preorder or postorder also gives sorted output for a BST - only inorder has that property.

Core lesson 03

Use DFS with two sets: 'visited' (fully processed) and 'in_progress' (on the current recursion stack); reaching a node already in in_progress means a cycle.

A simple 'visited' set alone isn't enough for directed graphs, because reaching an already-visited node doesn't necessarily mean a cycle - it might be a node reachable via multiple paths (common in DAGs). The signal is reaching a node still on the CURRENT path (an ancestor in the DFS tree), exactly what a back edge to an in-progress node means.

Python example
def has_cycle(graph):
    visited, in_progress = set(), set()
    def dfs(node):
        visited.add(node)
        in_progress.add(node)
        for neighbor in graph[node]:
            if neighbor in in_progress:
                return True             # back edge -- cycle
            if neighbor not in visited and dfs(neighbor):
                return True
        in_progress.remove(node)
        return False
    return any(dfs(node) for node in graph if node not in visited)

What to remember

How do you detect a cycle in a directed graph using DFS?

Common footguns

  • Forgetting to remove a node from in_progress when backtracking out of it - causes false-positive cycle detection on nodes reachable via multiple valid (acyclic) paths.

Python lab

Browser Python lab

Runtime · idle

Python loads on your first run. Your code stays in this browser.

Best practices

  • Use BFS for shortest path / level-order needs; DFS for exhaustive path exploration, cycle detection, and backtracking.
  • Remember: inorder traversal of a BST gives sorted values.
  • For directed-graph cycle detection, track 'in progress' nodes separately from 'visited'.
  • Convert a tree/grid problem to a graph problem mentally - most are graph problems in disguise.

References

LeetCode — Tree Explore CardNeetCode — Trees & Graphs Roadmap

Apply the concept in Interview practice

Binary Tree Level Order TraversalmediumLeetCode #102 · O(n) time

BFS with a queue, processing one full level (tracked by the queue's length at the start of each iteration) before moving to the next.

Open problem
Validate Binary Search TreemediumLeetCode #98 · O(n) time

DFS while passing down a valid (low, high) range for each node, or use inorder traversal and check values are strictly increasing.

Open problem
Number of IslandsmediumLeetCode #200 · O(rows·cols) time

DFS or BFS flood-fill from every unvisited land cell, marking connected land as visited; count how many times a flood-fill is triggered.

Open problem
Course SchedulemediumLeetCode #207 · O(V+E) time

Model prerequisites as a directed graph and detect a cycle - if there's a cycle, the courses can't all be completed.

Open problem
Lowest Common Ancestor of a Binary TreemediumLeetCode #236 · O(n) time

Recursively search both subtrees; if a node finds both targets in different subtrees, that node is the LCA.

Open problem

Concept checks

Q01

When should you use BFS instead of DFS?

Q02

What's the difference between preorder, inorder, and postorder tree traversal, and when does each matter?

Q03

How do you detect a cycle in a directed graph using DFS?