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

27 practiced

Explain visited-state management in graph traversals. Describe the differences between marking nodes visited on discovery (enqueue) versus when they are processed (dequeue), or using color states (white/gray/black). Discuss implications for correctness, duplicate work, cycle detection, multi-source traversal, and parallel traversals in SRE systems.

Sample Answer

Visited-state management ensures each graph node is handled correctly during traversals (BFS/DFS). Common strategies:

1) Mark-on-discovery (enqueue/enter)- When you first see a neighbor, mark visited and enqueue/stack it.- Correctness: avoids enqueueing duplicates; guarantees each node is scheduled once.- Duplicate work: minimal — prevents repeated exploration.- Cycle detection: you still need extra info to detect back-edges in DFS (see colors), but for BFS it prevents infinite loops.- Multi-source: easy — mark sources immediately to avoid re-adding same node.- Parallel: safer for concurrency because marking is done before work; requires atomic check-and-set to avoid races.

2) Mark-on-processing (dequeue/exit)- Only mark when you pop/process the node.- Correctness: still correct for many algorithms but may enqueue same node multiple times.- Duplicate work: can lead to redundant entries and repeated work, increasing memory/CPU.- Cycle detection: insufficient alone for detecting cycles in DFS.- Multi-source: risk of multiple enqueues from different sources.- Parallel: problematic — races create duplicate processing; needs deduplication.

3) Color states (white/gray/black)- White: unseen; Gray: discovered but not finished; Black: finished.- Correctness: precise for DFS cycle detection — encountering a gray node means a back-edge/cycle.- Duplicate work: avoids duplicates like mark-on-discovery, and additionally distinguishes in-progress vs finished which helps correctness in directed graphs.- Multi-source: handles coordination of discovery order cleanly.- Parallel: more expressive but requires atomic transitions; gray state helps detect concurrent re-discovery and avoid false cycle reports.

SRE implications:- Use mark-on-discovery or color states for distributed/parallel traversals with atomic operations to prevent duplicated work and wasted resources.- For cycle detection (dependency graphs, service call graphs), prefer color states in DFS.- For large-scale multi-source scans (service discovery, monitoring), mark-on-discovery reduces queue pressure.- In concurrent systems, implement idempotent processing and coordination (locks, CAS, centralized store like Redis) rather than relying on mark-on-processing.

EasyTechnical

34 practiced

Implement in Python a function shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int] that returns the shortest path (list of node ids) from start to target in an unweighted directed graph using BFS. If no path exists return an empty list. The graph is given as an adjacency list (nodes labeled 0..n-1). Aim for O(V+E) time and include path reconstruction. Example: adj = {0:[1,2],1:[2],2:[3],3:[]} start=0 target=3 => [0,2,3].

Sample Answer

Use BFS to find the shortest path in an unweighted directed graph and keep a parent map to reconstruct the path once target is reached.

python

from collections import deque
from typing import Dict, List

def shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int]:
    """
    Returns shortest path from start to target in directed unweighted graph using BFS.
    If no path exists returns [].
    """
    if start == target:
        return [start] if start in adj or start == target else []
    
    visited = set([start])
    parent = {}  # child -> parent
    q = deque([start])
    
    while q:
        node = q.popleft()
        for nei in adj.get(node, []):
            if nei not in visited:
                visited.add(nei)
                parent[nei] = node
                if nei == target:
                    # reconstruct path
                    path = [target]
                    while path[-1] != start:
                        path.append(parent[path[-1]])
                    path.reverse()
                    return path
                q.append(nei)
    return []

Key points:- BFS guarantees shortest path in unweighted graphs.- parent map enables O(length(path)) reconstruction.Time complexity: O(V + E). Space: O(V) for visited/parent/queue.

Edge cases:- start == target, missing nodes in adj, disconnected graph, cycles (handled by visited).

Alternative: run full BFS then reconstruct from parent if you prefer to wait until BFS completes; current code returns early when target found.

MediumTechnical

48 practiced

You must traverse a very large filesystem tree to find the top-k directories by cumulative size. Describe an algorithm and provide pseudocode (or Python sketch) for a streaming approach that uses O(k + h) memory (h = traversal stack depth). Explain how you handle symlink cycles, permission errors, and filesystems that change during traversal.

Sample Answer

Approach (brief)- Do an iterative DFS (post-order) so each directory’s cumulative size = sum of its files + children dirs.- Keep only O(h) traversal state (stack) and a min-heap of size k for top-k directories → O(k + h) memory.- Avoid symlink cycles by tracking visited (device, inode) pairs using os.lstat for symlink detection.- Handle permission errors and concurrent changes with try/except, best-effort sizes, and optional snapshotting notes.

Python sketch

python

import os, heapq, stat

def top_k_dirs(root, k):
    # min-heap of (size, path)
    topk = []
    # stack entries: (path, iterator, acc_size, visited_children_flag)
    stack = [(root, None, 0, False)]
    visited_inodes = set()  # (st_dev, st_ino)

    while stack:
        path, it, acc, done = stack.pop()
        try:
            st = os.lstat(path)
        except (OSError,) as e:
            # permission, missing file -> skip and continue
            continue

        key = (st.st_dev, st.st_ino)
        # skip cycles (symlink loops or hardlink revisit)
        if key in visited_inodes:
            continue
        visited_inodes.add(key)

        if not done:
            # push node back as "done" to accumulate after children
            stack.append((path, None, acc, True))
            if stat.S_ISDIR(st.st_mode):
                try:
                    it = os.scandir(path)
                except (OSError, PermissionError):
                    continue
                # push children
                for entry in it:
                    # use lstat to detect symlink vs actual file
                    try:
                        est = entry.lstat()
                    except (OSError,):
                        continue
                    if stat.S_ISDIR(est.st_mode) or stat.S_ISREG(est.st_mode) or stat.S_ISLNK(est.st_mode):
                        stack.append((entry.path, None, 0, False))
                # scandir iterator closed automatically
            else:
                # file or symlink: add its size
                try:
                    size = st.st_size
                except AttributeError:
                    size = 0
                # propagate size by adding to parent when popped as done
                stack.append((path, None, size, True))
        else:
            # node finished: compute cumulative size of this node by summing sizes of immediate entries
            # Use acc (for files) or sum sizes of children collected via visited_inodes? Simpler: gather sizes by checking children again is expensive.
            # Instead, we rely on pushing file entries and then parent accumulation via stack ordering:
            # When a child is pushed and later popped as done, its size entry is appended to parent's acc via stack ordering:
            # For clarity in production, maintain explicit parent references or a dict mapping path->size.
            # Here: use a small dict for sizes (still O(h) amortized since only active subtree sizes are kept).
            pass

Key implementation notes and reasoning- Use iterative DFS with explicit stack to control memory; post-order ensures children sizes are known before parent.- Maintain a small dict size_map for active paths to record cumulative sizes; remove entries when parent consumes them to keep memory ~O(h).- Min-heap (size k) keeps current top-k; push (size,path) and pop smallest when >k.- Symlink cycles: detect by (st_dev, st_ino) using lstat for symlinks. If you want to follow symlinks, resolve with stat and still check visited set.- Permission errors: catch Exceptions, log and skip; report skipped paths metric to caller.- Filesystem changes: this is best-effort. To be consistent, run on a snapshot (LVM/ZFS) or freeze filesystem. Otherwise accept race conditions (sizes may be stale) and surface a warning/metric.- Complexity: time proportional to number of entries visited; memory O(k + h + small active dict).

EasyTechnical

31 practiced

Explain breadth-first search (BFS) and depth-first search (DFS). Describe their algorithmic differences, the typical data structures used (queue vs stack/recursion), and practical SRE scenarios where you'd prefer one over the other (e.g., shortest unweighted path, dependency-depth analysis, reachability checks). Compare their time and space complexity and mention limitations for extremely deep or very wide graphs.

HardTechnical

34 practiced

Given multiple traversal logs produced by different traversals of a static binary tree (some logs might be incomplete/missing nodes), design an algorithm to determine whether there exists a binary tree consistent with all logs. Logs can be partial (missing subtrees). Describe how to model constraints induced by traversals and how to check consistency efficiently.

Sample Answer

Approach (high level):Model each traversal log as an ordered sequence of visited node IDs with possible gaps (missing subtrees). Each traversal type (pre, in, post, level) imposes partial order constraints between nodes. Reduce the problem to checking whether there exists a binary tree whose node-visitation orders are consistent with all partial orders induced by logs.

Modeling constraints:- Inorder: for any three nodes a,b,c if log shows a before b before c, then a is left of b and b is left of c in inorder sequence — equivalently, inorder defines a total left-to-right order for visited nodes; missing nodes only remove elements but preserve relative order.- Preorder/postorder: give ancestor-before-descendant or descendant-before-ancestor constraints when both appear in same log without gaps that would imply subtree boundaries.- Level-order: gives constraints on depth/parent relationships (nodes earlier cannot be in strictly deeper levels than later nodes beyond capacity of a binary tree).

Algorithm:1. Extract pairwise precedence constraints: for each log, for every i<j produce constraint node[i] ≺ node[j] in that traversal ordering.2. Map traversal constraints to binary-tree relations: - From inorder total order O, enforce left-to-right sequence. - For preorder P and inorder O, known theorem: unique tree exists if sequences are complete; with partial logs treat them as subsequences. Use subsequence consistency: P must be a subsequence of some preorder of a binary tree whose inorder is O.3. Reduce to graph reachability / 2-SAT style constraints: - Construct directed precedence graph G where edge u→v means u must appear before v in the tree's traversal order(s). - For inorder, impose total ordering edges among seen nodes. - For preorder/postorder, impose ancestor/descendant restrictions as edges between groups determined by inorder segments.4. Check for cycles in G. If G is acyclic and constraints can be embedded into a binary tree structure (validate with constructive attempt), return yes; else no.

Constructive check (efficient):- Use recursive reconstruction using inorder as backbone (if present). Treat unknown/missing nodes as wildcards. For each preorder log, try to partition inorder subsequence into root, left-subseq, right-subseq — root must be first preorder element that appears in inorder subsequence. Validate all logs by backtracking with memoization (DP on inorder intervals × subset of logs positions).- If no inorder log exists, pick any traversal as anchor and similarly attempt reconstruction.

Complexity and practical notes:- Worst-case is exponential due to partials; but with memoization DP over O(n^2) inorder intervals and log cursors the check is O(n^2 * L) where n = distinct nodes, L = number of logs/positions.- Pre-check: build precedence graph and detect cycles (O(n + m)). If cyclic, immediately reject.- Heuristics: prefer available inorder-like logs as backbone; prune using degree constraints (binary tree max children 2) and level-order depth bounds.

Edge cases:- Conflicting ancestor constraints (cycle) → inconsistent.- Completely partial logs (too little info) → many trees possible; return true.- Duplicate IDs or malformed logs → reject.

This approach balances formal constraint modeling (precedence graph + subsequence embedding) with a constructive DP/backtracking reconstruction for final validation—practical for SRE use when diagnosing inconsistent trace logs from distributed systems.

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.