Tree and Graph Algorithm Patterns for SWE Interviews

Tree and graph problems make up the largest single category of coding interview questions in 2026, appearing in roughly 35-40% of algorithmic rounds according to aggregated data from major interview prep platforms. The reason is structural: trees and graphs generalize to real engineering problems (dependency graphs, org charts, network routing, filesystem structures) in a way arrays and strings often don’t, so interviewers treat them as a proxy for whether a candidate can reason about non-linear data.

This guide covers the recurring patterns, not just individual problems, since pattern recognition — not memorization — is what separates candidates who can solve novel variants from those who can only regurgitate seen problems.

Pattern 1: Tree Traversal (DFS/BFS Foundations)

Every tree problem builds on the same three DFS traversal orders plus BFS. The pattern to internalize is when you process the current node relative to its children:

def dfs(node):
    if not node:
        return
    # preorder: process(node) here
    dfs(node.left)
    # inorder: process(node) here
    dfs(node.right)
    # postorder: process(node) here

• Preorder — use when you need to process a node before its children (e.g., serializing a tree, copying a tree)
• Inorder — for a BST, gives sorted order; use for validating BST properties or finding the kth smallest element
• Postorder — use when children must be fully processed before the parent (e.g., computing subtree size, deleting a tree, evaluating an expression tree)
• BFS (level order) — use whenever the problem is framed in terms of “level” or “depth” explicitly (e.g., right-side view, level averages, minimum depth)

The single most common interview mistake here is choosing DFS by default without checking whether the problem’s phrasing (“level,” “shortest path in an unweighted graph”) is a direct signal for BFS instead.

Pattern 2: Graph Traversal and Connectivity

Graphs generalize trees by allowing cycles and multiple parents. The two foundational traversals extend directly:

def bfs(start, graph):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

def dfs(node, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

Common variants tested in 2026 loops:

• Number of connected components / islands — DFS or BFS flood-fill, visited-set tracking
• Cycle detection — for undirected graphs, track parent to avoid false positives on the edge you just came from; for directed graphs, track a recursion stack (gray/white/black coloring) since a back edge to any visited node isn’t necessarily a cycle unless it’s on the current path
• Bipartite check — BFS/DFS with 2-coloring, fail if any edge connects same-colored nodes
• Topological sort — Kahn’s algorithm (BFS with in-degree tracking) or DFS with post-order reversal; this is the pattern behind build-dependency and task-scheduling problems

Pattern 3: Shortest Path Algorithms

Shortest path selection is one of the most commonly mis-applied patterns — candidates default to Dijkstra even when BFS suffices, or vice versa.

Dijkstra’s implementation with a min-heap:

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')):
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float('inf')):
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

Pattern 4: Union-Find (Disjoint Set Union)

Union-Find is the go-to structure whenever a problem asks about grouping/connectivity incrementally — as edges are added one at a time, rather than given the full graph upfront (which would just be a DFS/BFS problem).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected — would form a cycle
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

With path compression and union by rank, both operations run in effectively O(α(n)) — near-constant time. Union-Find shows up directly in: redundant connection detection, number of provinces/islands with incremental edges, Kruskal’s MST algorithm, and accounts-merge-style problems (grouping records by shared identifiers).

Comparison: When to Reach for Which Structure

Interview Execution Notes

Beyond knowing the algorithms, 2026 interview loops increasingly weight how you arrive at the pattern over whether you eventually land on correct code. Strong candidates narrate the signal-to-pattern mapping out loud (“this says ‘shortest path’ and the graph is unweighted, so BFS rather than Dijkstra”), which lets an interviewer follow your reasoning even if you stumble on implementation details. Candidates who silently code without narrating this mapping tend to score lower even when their final solution is correct, because the interviewer can’t distinguish “understood the pattern, made a typo” from “pattern-matched to a memorized solution without understanding why.”

This distinction — reasoning transparency over raw solution speed — is one of the most consistently misunderstood aspects of technical interviewing, and it’s covered in detail alongside a full set of tree/graph problem walkthroughs in The 0-to-1 SWE Interview Playbook, which breaks down the exact signal words interviewers use to telegraph which pattern they’re testing for.

FAQ

Q: Is it worth memorizing specific tree/graph problems, or should I focus on patterns? A: Patterns. Interview problems are frequently novel variants of the same underlying pattern (e.g., “rotting oranges” is BFS multi-source, same pattern as “walls and gates”). Memorizing exact problems fails the moment the variant changes.

Q: When should I use recursive DFS versus an explicit stack? A: Recursive DFS is cleaner and preferred unless the tree/graph depth could cause a stack overflow (very deep or unbalanced trees, or explicitly stated large input constraints), in which case an explicit stack avoids recursion-limit failures.

Q: How important is Union-Find compared to BFS/DFS in 2026 interviews? A: Less frequent than BFS/DFS but a strong differentiator — it shows up in a meaningful minority of graph problems (incremental connectivity, MST-adjacent problems) and candidates who reach for it immediately when the signal is present (edges added one at a time) stand out from those who default to re-running DFS from scratch each time.