Tree, Graph and Recursion Patterns: Traversal, BFS and DFS, Heaps, Tries, Backtracking, DP

Six patterns sit behind most tree, graph and recursion problems in coding interviews: tree traversal, graph search with BFS, DFS and topological sort, heaps and priority queues, tries, backtracking and dynamic programming. For each you get the signal that points to it, a short template, the classic problems to practice and the mistakes that cost the round. The companion page covers array and string patterns.

How to use this page

Each pattern has the signal that points to it, a short Python template, the classic problems to practice and the mistakes that cost the round. Trees and graphs make up a large share of interview problems, and recursion sits underneath both, so these six patterns are worth the most practice time. The array and string patterns are on the companion page, and our full list of LeetCode patterns covers union-find and more.

Trees

Tree traversal

Reach for it when the input is a binary tree or an n-ary tree. Decide first whether you need depth-first order (preorder, inorder, postorder) or level order with a queue; most tree problems are one traversal plus the right information returned from each call.

def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

from collections import deque
def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        out.append([n.val for n in q])
        q = deque(c for n in q for c in (n.left, n.right) if c)
    return out

Classic problems: Maximum Depth of Binary Tree, Invert Binary Tree, Binary Tree Level Order Traversal, Validate Binary Search Tree (inorder must be increasing), Lowest Common Ancestor, Binary Tree Maximum Path Sum, Serialize and Deserialize Binary Tree.

Mistakes that cost the round: returning the wrong thing from the recursive call (decide what each call returns before writing it), validating a BST by checking only parent and child instead of passing bounds down, and ignoring recursion depth on skewed trees.

Tries

Reach for it when the problem is about prefixes: autocomplete, word search across a board, or checking many words against a dictionary. A trie stores characters along paths, so prefix lookups cost the length of the word, not the number of words.

class Trie:
    def __init__(self): self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word: node = node.setdefault(ch, {})
        node['$'] = True
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node: return False
            node = node[ch]
        return True

Classic problems: Implement Trie, Design Add and Search Words Data Structure, Word Search II, Replace Words, Longest Word in Dictionary.

Mistakes that cost the round: forgetting the end-of-word marker, so prefixes look like whole words; rebuilding the trie inside a loop; and in Word Search II, not pruning found words, which leads to repeated work.

Graphs

Graph search: BFS, DFS and topological sort

Reach for it when the input is a grid, a network, dependencies or relationships. BFS gives shortest paths in unweighted graphs; DFS explores components and detects cycles; topological sort orders tasks with prerequisites.

from collections import deque
def shortest_steps(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    q, seen = deque([(start, 0)]), {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == goal: return d
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc)); q.append(((nr, nc), d + 1))
    return -1

Classic problems: Number of Islands, Clone Graph, Rotting Oranges, Pacific Atlantic Water Flow, Course Schedule I and II (topological sort), Word Ladder, Network Delay Time (Dijkstra for weighted edges).

Mistakes that cost the round: marking nodes visited when you pop them instead of when you push them, which floods the queue; using DFS for a shortest path in an unweighted graph; and missing disconnected components. For connectivity questions, union-find is often simpler.

Heaps

Heaps and priority queues

Reach for it when you need the k largest or smallest items, a running median, or to repeatedly take the next smallest item from several sorted sources. A heap gives O(log n) push and pop.

import heapq
def k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k: heapq.heappop(h)   # keep the k largest in a min-heap
    return sorted(h, reverse=True)

Classic problems: Kth Largest Element in an Array, Top K Frequent Elements, Merge k Sorted Lists, Find Median from Data Stream (two heaps), K Closest Points to Origin, Task Scheduler.

Mistakes that cost the round: using a max-heap of all n items when a min-heap of size k is enough, forgetting that Python's heapq is a min-heap (negate values for a max-heap), and not mentioning that sorting is O(n log n) while the size-k heap is O(n log k).

Recursion: backtracking and dynamic programming

Backtracking

Reach for it when the problem asks for all combinations, permutations, subsets or arrangements, or for any valid arrangement under constraints. Choose, explore, un-choose, and prune branches that cannot succeed.

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:]); return
        path.append(nums[i]); go(i + 1)   # choose
        path.pop(); go(i + 1)             # un-choose and skip
    go(0)
    return out

Classic problems: Subsets, Permutations, Combination Sum, Word Search, N-Queens, Palindrome Partitioning, Letter Combinations of a Phone Number.

Mistakes that cost the round: appending the path itself instead of a copy, forgetting to undo the choice, not sorting first when duplicates must be skipped, and not stating the exponential complexity.

Dynamic programming

Reach for it when the problem asks for a count, a minimum, a maximum or whether something is possible, and the answer for the whole input can be built from answers to smaller versions of it. Define the state, write the recurrence, then choose top-down with memoization or bottom-up with a table.

def coin_change(coins, amount):
    INF = amount + 1
    best = [0] + [INF] * amount        # best[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: best[a] = min(best[a], best[a - c] + 1)
    return best[amount] if best[amount] != INF else -1

Classic problems: Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, Longest Common Subsequence, Word Break, Edit Distance, Partition Equal Subset Sum.

Mistakes that cost the round: starting to code before the state is defined in one sentence, which is the single most common failure; getting the base cases wrong; and not offering the space optimization when only the previous row is needed.

How to explain a recursive solution out loud

1. Say what one call returns, in one sentence, before writing it: "the depth of this subtree" or "the fewest coins to make this amount".
2. State the base case and why it is correct.
3. Walk through a small example by hand, three or four nodes or a small amount.
4. Give time and space, counting the recursion stack as space.
5. Offer the next step: iterative traversal for deep trees, a smaller table for dynamic programming, pruning for backtracking. For a full study list, the NeetCode 150 roadmap groups problems by these patterns.

Where CoPilot Interview fits

Knowing a pattern and explaining it under time pressure are different skills, and coding rounds score both. CoPilot Interview is an AI interview assistant; its free AI mock interview asks tree, graph and dynamic programming problems against your résumé and the job description, reads them aloud and scores your spoken explanation out of ten, which is the part most people never practice. The free plan gives 15 minutes a day of live help in sessions of up to 15 minutes, with AI mock interviews included. In a real coding round, follow your employer's rules: many online assessments and live coding screens forbid outside help, and the invitation usually says so.

Disclosure: CoPilot Interview is our product, so weigh what we say about it accordingly.

Frequently asked questions

Which of these patterns is asked most?

Tree traversal and graph search appear in most coding loops, and dynamic programming is common at large tech companies for mid-level and senior roles. Heaps show up in top-k and scheduling questions, and tries mostly in string and search problems.

Recursive or iterative?

Write the version you can get right first, which is usually recursive, then mention the iterative version if depth could be a problem. Some interviewers ask for iterative inorder traversal specifically, so practice it once.

How do I get better at dynamic programming?

Solve problems in families, such as the knapsack problems, the subsequence problems and the grid path problems, and for each write the state in one sentence before any code. Most dynamic programming failures are an unclear state, not weak coding.

When should I use union-find instead of BFS or DFS?

When the question is about connectivity that changes as edges are added, such as counting components or detecting a cycle while building a graph. For shortest paths, use BFS or Dijkstra.

Where are the old single-pattern pages?

Each of the six patterns that used to be a separate page now lives in a section of this page, and the old addresses redirect to the matching section.