Choosing a tree or graph traversal

When an interviewer hands you a tree or a graph, the first two minutes decide most of the round. Pick the visiting order that matches what each node needs and the code is a dozen lines. Pick the wrong one and you end up passing lists through the recursion and patching cases at the end. After this page you can hear a prompt, name the structure, choose the order or search that fits, and state its cost before you type.

Ask which kind of tree you have

In a tree, every node except the root has exactly one parent and can be reached from the root, so there are no cycles. "Tree" alone tells you little, and interviewers often leave the qualifier out to see whether you ask. Below, n is the number of nodes and h is the height: the number of edges on the longest root-to-leaf path.

A BST nobody rebalances can degrade into a chain (h = n - 1), and every O(h) becomes O(n). Python's default recursion limit is 1,000 frames, so a recursive walk down a 100,000-node chain raises RecursionError.

"Is this a binary search tree or any binary tree? Can keys repeat? Could it be one long chain? If so, I'll use an explicit stack instead of recursion."

Choose the order from what each node needs

Every depth-first walk of a binary tree visits each node once: O(n) time and O(h) extra space for the stack. The orders differ only in when a node does its own work relative to its children; let the question decide.

Pre-order fits "count the nodes at least as large as every node above them": each node needs the largest value on its path, its parent already knows it, so you pass it down as an argument. In-order gives sorted keys only on a BST; on any other binary tree it is just left-to-right order.

Post-order runs the other way. Take "count the subtrees in which every node holds the same value". A node cannot answer until it knows whether each child's subtree is uniform, so both children report first:

def count_uniform(root):
    """Count subtrees in which every node holds the same value."""
    count = 0

    def uniform(node):
        nonlocal count
        if node is None:
            return True
        left_ok = uniform(node.left)     # both children report first
        right_ok = uniform(node.right)
        if not (left_ok and right_ok):
            return False
        for child in (node.left, node.right):
            if child is not None and child.val != node.val:
                return False
        count += 1
        return True

    uniform(root)
    return count

"Each node needs both children's answers before it can decide, so the children finish first: post-order. One pass, O(n) time, and O(h) stack, which is O(n) if the tree is a chain."

The bug interviewers catch here is if not (uniform(node.left) and uniform(node.right)). Python's and stops at the first False, so when the left subtree is mixed, the right subtree is never visited and its uniform subtrees go uncounted. The interviewer sees a count too low on any tree with a mixed left side. Call both children, keep both answers, then combine.

Heaps and tries: trees you use for their shape

A binary heap is a complete binary tree in which every parent is no larger than its children, so the smallest item sits at the root. Being complete, it lives in a plain list, which is what Python's heapq works on. For a heap of n items:

heapq only builds min-heaps; for the largest first, push negated keys. Use a heap when you keep needing the smallest item of a changing set. To merge k log files already sorted by time, keep each file's next unread entry in the heap: N entries in total cost O(N log k) time, with at most k items in the heap. Push (timestamp, file_index, position), not (timestamp, message): on a tie, Python compares the next field, and two dict messages raise TypeError.

A trie (say "try") is a tree of characters. Each edge is one character, so words that share a prefix share a path from the root. Looking up a word or prefix of length L takes O(L) steps however many words are stored. A hash set answers whole-word lookups as fast, but cannot say how many stored words start with "ca" without scanning them all. Use a trie when the question is about prefixes:

class TrieNode:
    def __init__(self):
        self.children = {}   # character -> TrieNode
        self.passing = 0     # words inserted through this node
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        node.passing += 1
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.passing += 1
        node.is_word = True

    def count_prefix(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return 0
        return node.passing

An insert costs O(L), and the trie holds at most one node per character inserted: O(C) space for C characters in total.

Store a graph as a list of neighbors

A graph is nodes and edges with no rule against cycles. Edges may be directed (one-way) or undirected, weighted or not; ask which. Here n is the number of nodes, m the number of edges and deg(u) the number of edges at node u.

Use the list unless the graph is dense (m near n²). In Python that is a defaultdict(list); append both directions for an undirected edge. A node with no edges never appears in an edge list, so when the prompt gives you n, loop over range(n), not the dict's keys. Some graphs are never stored: grid cells and puzzle positions are nodes whose neighbors you generate on demand.

Depth-first or breadth-first

Both take O(n + m) time with an adjacency list. What usually decides it is whether the prompt wants the fewest of something. BFS reaches nodes in order of distance, so when it first adds a node, it has the fewest edges to it; DFS finds a path, not the shortest. Suppose a config change starts on one server and each server passes it to its direct peers once a second. When does each server get it?

from collections import deque

def hops_from(graph, source):
    """Fewest edges from source to every node it can reach."""
    dist = {source: 0}             # doubles as the visited set
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for nxt in graph.get(node, ()):
            if nxt not in dist:    # mark when added, not when popped
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

"The links have no weights and I want the fewest hops, so breadth-first search with a deque. I mark a server visited when I add it to the queue, so each one enters once: O(n + m) time for n servers and m links, O(n) memory."

The mistake interviewers see most is marking a node visited when it is popped, not when it is added. A node then enters the queue once per edge that reaches it before its turn, so the queue can grow to m entries, each expanded again unless skipped. With no visited check at all, two neighbors in an undirected graph hand each other back and forth forever. And list.pop(0) costs O(n) per pop; the stack and queue lesson explains why deque fixes it.

When edges carry weights, fewest edges is no longer cheapest. If no weight is negative, swap the queue for a heap keyed on distance so far (Dijkstra's algorithm), O((n + m) log n); a negative edge breaks it, and Bellman-Ford, O(n · m), is the usual answer. When edges mean "must happen before" and there are no cycles, the nodes can be listed in a topological order, in which every edge points forward.

Search from both ends when the graph is huge

If each node has about b neighbors, BFS from one end explores on the order of b^d nodes to reach a target d edges away. When you know the exact target and can walk edges backwards, run two searches, one from each end, and stop when they meet. Each goes about d/2 deep, so the total is on the order of 2 × b^(d/2).

A puzzle cube shows the gap. Every position has 18 single turns, and every turn can be undone, so the graph is undirected. For a scramble 10 turns from solved, one search could touch on the order of 18^10, about 3.6 trillion positions. Two searches meeting halfway touch on the order of 2 × 18^5, about 3.8 million.

You need one known target and a way to list a node's predecessors: free with undirected edges, while one-way links need the reverse edges stored too. Expand a whole level at a time from whichever side has the smaller frontier, and test each new node against everything the other side has seen. Alternating one node at a time and stopping at the first touch can return a path longer than the shortest.

Practicing with these questions

Before you write code for any card here, say one sentence naming the structure (which kind of tree, or which kind of graph and how you will store it), the order or search, what you mark visited or what each node returns, and the cost in n and m. If you can't say it, you are not ready to type. Then code it and trace a four-node input by hand, including a node with no children or no edges.

Work Order Lead Time: Critical Path Through an Operations DAG to Shipping tests that habit well: its plan is harder to say than its code is to write. For more repetitions, do the Blind 75 graph problems the same way.