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

30 practiced

Explain how you manage visited state during graph traversal to avoid infinite loops in cyclic graphs. Provide a short discussion for (a) DFS recursion, (b) DFS iterative, and (c) BFS. In addition, explain the subtle difference between marking visited when you push/enqueue a node vs when you pop/dequeue it and the consequences for multi-edge and directed graphs.

Sample Answer

Core idea: keep a visited set (or color states) so when you reach a node already being explored you don't re-traverse it—this prevents infinite loops in cyclic graphs.

(a) DFS recursion:- Typical pattern: mark node as visited when you enter the recursive function (pre-visit). Recurse on unvisited neighbors. This prevents revisiting ancestors in cycles.- For cycle detection in directed graphs use 3 colors: white (unseen), gray (on recursion stack), black (finished). Seeing a gray node => back-edge => cycle.

(b) DFS iterative:- Use an explicit stack. Best practice is to mark a node when you push it onto the stack (not when you pop) so you avoid pushing the same node many times from different neighbors. If you need post-order processing (after children), you can push a marker or use two-phase entries (push node then push sentinel), but still mark on first discovery.

(c) BFS:- Use a queue and mark when you enqueue. This guarantees each node is enqueued once and that the first time you see a node gives the shortest-path distance in unweighted graphs. Mark-on-dequeue would allow multiple enqueues from different parents, extra work, and can break shortest-path logic.

Subtle difference (mark on push/enqueue vs pop/dequeue):- Mark-on-push/enqueue = “discovered” semantics: avoids duplicates, reduces memory and work, preserves BFS shortest-path property.- Mark-on-pop/dequeue = “processed” semantics: allows multiple pending entries for the same node; useful only if you need to consider multiple paths before deciding (rare) or implement certain algorithms that require seeing all incoming edges first.- Consequences for multi-edge/direct graphs: with multiple parallel edges, mark-on-pop will allow duplicates and redundant processing; in directed graphs color/stack semantics matter for correct cycle detection—marking as soon as discovered (gray) prevents false positives and redundant traversals, while black indicates fully processed.

Practical note for data engineering: in distributed traversals (Spark/graph-parallel), maintain discovery state across iterations (e.g., BFS frontier) rather than relying on recursion; always prefer discovery-time marking to limit work and memory.

EasyTechnical

33 practiced

Compare adjacency list and adjacency matrix representations for graphs. For a graph with n nodes and m edges, describe memory and time complexity for common operations (iterate neighbors, check edge existence, add/remove edges). As a data engineer designing storage for graphs with billions of edges, explain when you would use compressed formats like CSR/CSC or edge lists and how sparsity/density affects the choice.

Sample Answer

Adjacency list vs adjacency matrix — quick comparison (graph with n nodes, m edges; assume directed unless noted):

Memory- Adjacency matrix: O(n^2) memory (dense n×n). Good only when n is small or graph is dense (m ≈ n^2).- Adjacency list: O(n + m) memory (store a list/array of neighbors per node). Scales for sparse graphs (m << n^2).

Common operations- Iterate neighbors of node u: - Matrix: O(n) to scan row (even if few neighbors). - List: O(deg(u)) — optimal when deg(u) small.- Check edge existence (u,v): - Matrix: O(1) lookup. - List: O(deg(u)) if unsorted; O(log deg(u)) if neighbor lists are sorted or hashed.- Add edge: - Matrix: O(1). - List: O(1) amortized (append); O(log deg) if kept sorted.- Remove edge: - Matrix: O(1). - List: O(deg(u)) to find and remove; O(1) if using a hash-set per adjacency but higher memory.

At billion-edge scale (data-engineer view)- Use compressed sparse row (CSR) / compressed sparse column (CSC) when graph is large and sparse: - Memory: compact arrays — offsets + concatenated neighbor list ≈ O(n + m). - Extremely cache-friendly and efficient for sequential neighbor iteration and matrix-vector ops (good for analytics, graph algorithms in Spark/SciPy). - Read-only or mostly-read workloads benefit most (updates/inserts are expensive—require rebuilding).- Use edge lists (sorted or partitioned) when: - Storing raw ingestion streams, performing bulk transformations, or loading into distributed systems (Parquet/ORC tables partitioned by source/dest). - Good for append-heavy pipelines and distributed joins; index needed for fast neighbor access.- Sparsity vs density: - Sparse (m ≪ n^2): CSR/CSC or adjacency lists — lowest memory, best for traversal/analytics. - Dense (m ≈ n^2): adjacency matrix or block-dense representations (bitsets, GPU-friendly dense tensors) may be simpler and faster for constant-time edge checks and linear algebra.Practical trade-offs: favor CSR/CSC for billion-edge analytics when updates are batched; use partitioned edge lists/columnar storage for ingestion and ETL; choose representations that match access pattern (random edge checks vs full-neighbor scans) and operational constraints (update frequency, memory, distributed processing).

MediumTechnical

29 practiced

Given an edge list for an undirected graph, implement connected components using Union-Find (disjoint set union) in Python. Provide def count_components(edges: List[Tuple[int,int]]) -> int that returns the number of components. Use path compression and union by rank and discuss time complexity on large datasets.

Sample Answer

Approach: build a Union-Find over all nodes seen in the edge list, union each edge (u,v) with union-by-rank and path compression, then count distinct roots.

python

from typing import List, Tuple

def count_components(edges: List[Tuple[int,int]]) -> int:
    # Collect unique nodes
    nodes = set()
    for u, v in edges:
        nodes.add(u); nodes.add(v)
    if not nodes:
        return 0

    # Map node -> index (optional, but keeps DSU compact)
    idx = {node:i for i,node in enumerate(nodes)}
    n = len(nodes)
    parent = list(range(n))
    rank = [0]*n

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

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        # union by rank
        if rank[ra] < rank[rb]:
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1

    for u, v in edges:
        union(idx[u], idx[v])

    # Count distinct roots
    roots = {find(i) for i in range(n)}
    return len(roots)

Key points:- Path compression in find reduces tree height; union by rank keeps trees balanced.- Time complexity: nearly O(alpha(N)) per operation (inverse Ackermann), so for E unions and up to N finds total ~O((N+E) * α(N)) which is effectively linear for practical sizes.- Space: O(N) for parent/rank.- Edge cases: empty edge list -> 0; isolated nodes not present in edges won't be counted—if you must include isolated nodes, accept a nodes list input or include them in edges as (x,x) or add separately.- Scalability notes: for very large graphs, stream edges, map node IDs to integers incrementally, and shard unions if using distributed frameworks (use graph partitions + final merge of DSU summaries or use Spark GraphX/connected components algorithms).

EasyTechnical

27 practiced

Explain the difference between breadth-first search (BFS) and depth-first search (DFS). In a data engineering context, describe which traversal you would choose for tasks such as (a) finding shortest path in an unweighted graph, (b) exploring dependency graphs to detect cycles, and (c) scanning a very large graph where memory is limited. Discuss typical data structures used, time and space complexity, and practical tradeoffs for production pipelines.

Sample Answer

BFS vs DFS — concise definitions:- BFS (breadth-first search) explores a graph level by level from a start node, using a queue. It finds shortest path in terms of edge count in unweighted graphs.- DFS (depth-first search) explores by going deep along a branch before backtracking, typically implemented with a stack (or recursion).

Which to use:(a) Shortest path in an unweighted graph: BFS. Because it visits nodes in increasing distance order, the first time you reach the target is a shortest path (edges count). Use a queue + visited set; time O(V+E), space O(V) for visited/queue.(b) Detecting cycles in dependency graphs: DFS is preferable. Use DFS with coloring (white/gray/black) or recursion stack to detect back edges that indicate cycles. Time O(V+E), space O(V) for recursion/stack and seen sets.(c) Scanning a very large graph with limited memory: Prefer an external-memory or streaming approach; iterative DFS using an explicit stack can use less frontier memory than BFS in wide graphs, but both can still be large. Use techniques: graph partitioning, bloom filters for visited set, probabilistic sampling, or distributed frameworks (Spark/GraphX, Gelly) that process partitions. For single-machine, use disk-backed queues or iterative deepening DFS to limit memory at the cost of repeated work.

Typical data structures:- Adjacency lists (sparse graphs) stored in-memory or on disk; adjacency matrices only for dense graphs.- Queue for BFS, stack/recursion for DFS, visited set (hash set) or bitset.

Practical tradeoffs for production pipelines:- Memory: BFS can blow up when graph has high branching factor; prefer streaming/partitioned or disk-backed BFS. DFS may cause deep recursion—use iterative stack to avoid recursion limits.- Parallelism: BFS lends itself to level-synchronous parallel processing (good for distributed frameworks). DFS is inherently sequential but can be parallelized across components.- Determinism & reproducibility: Choose stable traversal order or sort neighbors to ensure repeatable results for ETL jobs.- Failure/restart: Use checkpointing or idempotent visited-state storage (e.g., in a key-value store) for long-running traversals.- Tooling: Use graph processing engines for large graphs and avoid pure in-memory algorithms unless data fits.

Edge cases: disconnected graphs (run traversal from all nodes), graphs with millions of nodes (use distributed processing), and weighted shortest paths (use Dijkstra/A* instead of BFS).

MediumTechnical

39 practiced

Implement Kosaraju's algorithm to compute strongly connected components (SCCs) of a directed graph in Python. Provide def kosaraju_scc(graph) -> List[List[int]] where graph is adjacency list. Discuss complexity and memory usage and mention iterative vs recursive implementations for deep graphs.

Sample Answer

Approach: Run Kosaraju — (1) DFS to produce vertices in finish-time order, (2) reverse graph, (3) DFS in order of decreasing finish time on reversed graph to collect SCCs. I'll provide an iterative DFS implementation (safer for deep graphs used in data pipelines).

python

from typing import List, Dict, Union

def kosaraju_scc(graph: Union[Dict[int, List[int]], List[List[int]]]) -> List[List[int]]:
    """
    Returns list of SCCs (each SCC is a list of node ids).
    Accepts adjacency as either dict<int, List<int>> or list of lists (0..n-1).
    Iterative to avoid recursion limits.
    """
    # Normalize to dict form
    if isinstance(graph, list):
        g = {i: neigh for i, neigh in enumerate(graph)}
    else:
        g = graph

    nodes = list(g.keys())
    for u in list(g.keys()):
        for v in g[u]:
            if v not in g:
                g.setdefault(v, [])  # ensure all nodes present

    visited = set()
    order = []

    # Iterative DFS to compute finish order
    for start in g:
        if start in visited:
            continue
        stack = [(start, 0, False)]  # (node, next_child_index, expanded_flag)
        parent_iter = {}  # map node -> children list for index access
        while stack:
            node, idx, expanded = stack.pop()
            if node in visited and not expanded:
                continue
            if not expanded:
                visited.add(node)
                children = g.get(node, [])
                parent_iter[node] = children
                # push node back marked as expanded so we add to order after children processed
                stack.append((node, 0, True))
                # push children
                for nbr in reversed(children):  # reversed to mimic recursive order
                    if nbr not in visited:
                        stack.append((nbr, 0, False))
            else:
                order.append(node)

    # Build reversed graph
    rev = {u: [] for u in g}
    for u, neigh in g.items():
        for v in neigh:
            rev[v].append(u)

    # Second pass: collect SCCs
    visited.clear()
    sccs = []
    for node in reversed(order):
        if node in visited:
            continue
        comp = []
        stack = [node]
        visited.add(node)
        while stack:
            u = stack.pop()
            comp.append(u)
            for v in rev.get(u, []):
                if v not in visited:
                    visited.add(v)
                    stack.append(v)
        sccs.append(comp)
    return sccs

Key points:- Time complexity: O(V + E) — each edge/node visited a constant number of times.- Space complexity: O(V + E) for adjacency + O(V) for visited/order/stacks.- Iterative vs recursive: recursive DFS is simpler but risks Python recursion limits on deep graphs (common in ETL job dependency graphs or long chains). Iterative stack-based DFS avoids recursion limits and is preferable in production data systems. For extremely large graphs, consider streaming/partitioning or graph frameworks (GraphX, Pregel-style) to distribute computation. Edge cases: isolated nodes, nodes referenced but not keys, empty graph.

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.