Tree and Graph Traversal Questions

Comprehensive mastery of tree and graph traversal algorithms, representations, and common interview problem patterns. Understand graph models and representation choices including adjacency lists versus adjacency matrices and trade offs based on sparsity and density, as well as properties such as directed versus undirected and weighted versus unweighted edges. Know visited state management to avoid cycles and techniques for cycle detection. Implement breadth first search and depth first search in both recursive and iterative forms, understand when to use a queue versus a stack, and analyze time and space complexity. Apply traversals to problems such as shortest path in unweighted graphs, connected component detection, topological sort for dependency ordering, cycle detection, path existence, and island counting. For trees, master traversal orders including in order, pre order, post order, and level order with both recursive and iterative implementations, including explicit stack based approaches and constant space approaches where relevant. Practice tree specific problems such as lowest common ancestor, path sum, tree serialization and deserialization, validating binary search trees, balancing and reconstruction of trees from traversal sequences, and converting between tree and graph formulations. Emphasize clean code, correctness, handling edge cases such as empty or skewed structures, recursion base cases and depth limits, and explaining trade offs between recursion and iterative solutions with respect to performance and memory.

EasyTechnical

35 practiced

Describe strategies for managing visited state when traversing graphs to avoid cycles. Cover: visited sets, boolean arrays, on-stack markers for directed graphs, in-place marking (when possible), and memory-efficient representations (bitset, bloom filters). Explain trade-offs between correctness, memory, and false positives or modification of input when using approximate methods.

Sample Answer

Start with a clear goal: prevent revisiting nodes (and detect cycles) while balancing correctness, memory, and whether you may modify the input.

Common strategies

1. Visited set (hash set)- Use a hash set of node IDs (or pointers) to mark visited nodes during DFS/BFS.- Correctness: exact, no false positives.- Memory: O(N) extra memory; flexible for sparse or non-indexed graphs.

2. Boolean arrays- If nodes map to contiguous indices [0..N-1], use a boolean array.- Correctness: exact, very fast lookups.- Memory: O(N) bits/bytes — lower overhead than hash sets and better cache behavior.

3. On-stack markers (for directed graphs / cycle detection)- Maintain two markers: visited (permanent) and onStack (current recursion path).- If DFS reaches a node onStack → back-edge → cycle.- Correctness: exact for directed cycle detection; needed to distinguish back edges from cross edges.

4. In-place marking (mutating node fields)- When you can modify graph objects (temporary flags), store visited/onStack in node fields.- Memory: zero extra allocation.- Trade-off: destructive unless you restore fields; unsafe if graph is shared/immutable.

5. Memory-efficient representations- Bitset / bit-array: pack booleans into bits to reduce memory (N/8 bytes).- Bloom filter: probabilistic membership test with configurable false-positive rate. - Memory: much smaller than exact sets. - Trade-offs: false positives can prematurely prune traversal (may miss reachable nodes or mis-detect cycles). Not suitable when correctness is required; okay for heuristic exploration or very large graphs where occasional misses are acceptable.

Trade-offs summary- Correctness vs. memory: exact methods (sets, arrays, in-place) guarantee correctness but cost O(N) memory. Bitsets reduce constant factor. Bloom filters save memory but introduce false positives — unacceptable for algorithms that must visit every reachable node or deterministically detect cycles.- Mutating input vs. isolation: in-place marking saves memory but risks side effects; require careful restore or copies for shared/immutable graphs.- Performance: boolean arrays and bitsets are fastest and cache-friendly; hash sets have higher overhead.

Recommendation for AI Engineer- Prefer boolean arrays or bitsets when nodes are indexable and correctness matters (e.g., graph-based search for inference, data-flow analysis).- Use onStack markers for directed cycle detection.- Use bloom filters only for best-effort, memory-constrained exploratory passes where false negatives are unacceptable but occasional false positives are tolerable and can be mitigated by a later exact verification pass.

EasyTechnical

35 practiced

Implement depth-first search (DFS) for a directed graph both recursively and iteratively in Python. Input: adjacency list dict and a start node id. Output: list of nodes in the order first visited. The iterative version should use an explicit stack and avoid recursion depth limits. Explain time and space complexity and differences in traversal order between the two approaches.

Sample Answer

To implement DFS from an adjacency-list dict starting at a given node, we can write both recursive and iterative versions that record the order nodes are first visited. The iterative version uses an explicit stack to avoid recursion limits.

Recursive approach (simple, natural):

python

def dfs_recursive(adj, start):
    visited = set()
    order = []

    def dfs(u):
        visited.add(u)
        order.append(u)
        for v in adj.get(u, []):
            if v not in visited:
                dfs(v)

    dfs(start)
    return order

Iterative approach (explicit stack; push neighbors in reverse order to match recursive visit order):

python

def dfs_iterative(adj, start):
    visited = set()
    order = []
    stack = [start]

    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        # Push neighbors in reverse so the left-most neighbor is processed first,
        # which makes traversal order closer to recursive DFS.
        neighbors = adj.get(u, [])
        for v in reversed(neighbors):
            if v not in visited:
                stack.append(v)
    return order

Key points:- Time complexity: O(V + E) for both (visit each node and edge once).- Space complexity: O(V) for visited and call stack / explicit stack (worst-case depth V).- Traversal order: Recursive DFS follows adjacency iteration order. Iterative DFS can produce the same order if you push neighbors onto the stack in reverse of the adjacency order; otherwise order differs. Iterative is preferred when recursion depth may exceed Python's limit or when explicit stack control is needed.- Edge cases: start not in adj (handled by adj.get), disconnected graph (these functions only traverse reachable nodes from start), graphs with cycles (visited set prevents infinite loops).

MediumTechnical

28 practiced

Implement serialize and deserialize functions for a binary tree using level-order (BFS) representation. The serializer should produce a compact string format (eg. comma-separated values with null markers) and deserializer should rebuild the exact tree structure. Discuss how this format handles missing children and why BFS is convenient for networks and streaming.

Sample Answer

Approach: Use level-order BFS to serialize nodes into a compact comma-separated string. Represent null children with a sentinel (e.g., "#"). During deserialization, reconstruct level-by-level using a queue to assign left/right children in the same order.

python

from collections import deque

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

def serialize(root):
    """Return CSV string of level-order nodes; use '#' for nulls."""
    if not root:
        return ""
    q = deque([root])
    parts = []
    while q:
        node = q.popleft()
        if node:
            parts.append(str(node.val))
            q.append(node.left)
            q.append(node.right)
        else:
            parts.append('#')
    # Trim trailing null markers to keep string compact
    while parts and parts[-1] == '#':
        parts.pop()
    return ",".join(parts)

def deserialize(data):
    """Rebuild tree from level-order CSV with '#' as null marker."""
    if not data:
        return None
    parts = data.split(',')
    root = TreeNode(int(parts[0]))
    q = deque([root])
    i = 1
    while q and i < len(parts):
        node = q.popleft()
        # left child
        if parts[i] != '#':
            node.left = TreeNode(int(parts[i]))
            q.append(node.left)
        i += 1
        # right child (check bounds)
        if i < len(parts) and parts[i] != '#':
            node.right = TreeNode(int(parts[i]))
            q.append(node.right)
        i += 1
    return root

Key concepts:- Null markers preserve exact shape (including missing children).- Trimming trailing '#' reduces size without losing structure because trailing nulls add no new children.Time/Space:- Serialization and deserialization are O(n) time and O(n) space (queue + output).Why BFS is convenient for networks/streaming:- BFS produces a predictable, ordered stream of nodes suitable for chunked transmission; each token corresponds to a known position in the tree, enabling partial reconstruction and streaming parsers. It minimizes context needed to append children and aligns with layer-wise processing common in distributed or pipeline systems. Edge cases: empty tree, single node, trees with many missing internal children, non-integer values (use escaping/encoding).

EasyTechnical

38 practiced

Implement breadth-first search (BFS) in Python. Input: adjacency list as a dict mapping node ids to lists of neighbor ids, and a start node id. Output: a tuple (order, dist) where order is list of nodes in visitation order by level and dist is a dict mapping node -> minimum edge distance from start. Your solution should run in O(n + m) time and handle disconnected nodes gracefully.

Sample Answer

To implement BFS, we use a queue to explore the graph level by level, track visited nodes to avoid repeats, record visitation order, and compute shortest-edge distances from the start. For disconnected nodes, include them in the dist dict with value None.

python

from collections import deque

def bfs(adj, start):
    """
    adj: dict[node] -> list[neighbor nodes]
    start: start node id
    Returns: (order, dist) where
      - order: list of nodes in visitation order by level
      - dist: dict mapping every node in adj -> minimum edge distance from start (None if unreachable)
    Runs in O(n + m) time.
    """
    order = []
    dist = {node: None for node in adj}    # initialize distances to None for disconnected nodes
    if start not in adj:
        # If start not in graph, return empty order and unchanged dist
        return order, dist

    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj.get(u, []):
            if dist[v] is None:      # not visited yet
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

Key points:- Uses deque for O(1) pops/pushes.- Initializes dist for every node so disconnected nodes are represented as None.- Time complexity O(n + m): each node visited once, each edge examined once.- Space complexity O(n) for dist/visited and O(n) worst-case for queue.

Edge cases:- start not in adj (handled).- isolated nodes (remain dist None).- self-loops and parallel edges handled since visited check prevents repeats.

Alternative: return dist for visited nodes only (omit unreachable) or use float('inf') instead of None to represent unreachable.

MediumTechnical

35 practiced

You have a very deep tree or a graph that could trigger Python recursion depth errors (depth > 10k). Describe and implement approaches to safely traverse such structures in production, including converting recursive DFS to iterative, using explicit stacks, tail-call elimination alternatives, and streaming traversal to reduce memory.

Sample Answer

Situation: In AI pipelines I often traverse very deep model-search trees or large computation graphs (depth >10k) where Python recursion hits RecursionError and memory/latency matter.

Approach summary:- Avoid recursion in Python: convert DFS to iterative using an explicit stack.- Use generators/streaming to process nodes incrementally and reduce memory.- Use tail-call elimination alternatives (trampolines or convert tail recursion to loops).- As a last resort, increase recursion limit or use PyPy/c extensions (cautioned for production).

Iterative DFS (explicit stack):

python

def iterative_dfs(root):
    # root has attribute .children (iterable)
    stack = [root]
    while stack:
        node = stack.pop()
        yield node  # streaming: process one node at a time
        # push children in reverse if order matters
        for child in reversed(node.children):
            stack.append(child)

Trampoline for tail-recursive-like flows:

python

def trampoline(fn, *args, **kwargs):
    f = fn(*args, **kwargs)
    while callable(f):
        f = f()
    return f

# Example tail-style function returns a lambda to continue
def sum_tail(n, acc=0):
    if n == 0:
        return acc
    return lambda: sum_tail(n-1, acc+n)
# trampoline(sum_tail, 100000)  # safe in Python (avoids deep recursion)

Streaming / generator pipeline (reduce memory and enable batching):

python

def stream_nodes(root):
    stack = [root]
    while stack:
        node = stack.pop()
        yield node
        for c in node.children:
            stack.append(c)

# downstream consumer processes in batches for GPU:
batch = []
for node in stream_nodes(root):
    batch.append(prepare_tensor(node))
    if len(batch) == BATCH_SIZE:
        model.train_on_batch(batch)
        batch.clear()

Key trade-offs & advice:- Iterative DFS uses O(depth) stack in Python heap; tail-trampoline converts recursion into loop but needs function-wrapping overhead.- Streaming yields low memory but possibly more I/O/context switches.- Avoid increasing recursion limit in production unless tested; prefer iterative/trampoline.- For graphs with cycles, maintain a visited set to avoid infinite loops.- For extreme depth and performance-critical code, implement traversal in C/Cython or use iterative algorithms in libraries.

Unlock Full Question Bank

Get access to hundreds of Tree and Graph Traversal interview questions and detailed answers.

Join thousands of developers preparing for their dream job.