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

28 practiced

Compare adjacency list vs adjacency matrix representations. For each representation provide memory complexity, common operations (iterate neighbors, edge lookup), and discuss trade-offs for sparse vs dense graphs and typical machine learning applications (GNN input, similarity matrices, embedding graphs).

HardTechnical

34 practiced

You need to convert recursive tree-traversal model code into a vectorized approach for batch inference across many trees (e.g., in a batch of XGBoost models). Describe techniques to transform traversal into SIMD-friendly operations or table lookups and discuss memory layout and cache effects.

Sample Answer

Approach / framing:Convert per-sample recursive tree traversal into batch, SIMD-friendly operations by removing recursion/branches and exposing parallelism across samples and trees. Goal: maximize data-parallel comparisons, minimize branch mispredictions and cache misses.

Techniques to transform traversal:- Flatten trees into arrays (BFS/level-order) so children indices are arithmetic offsets; represent each node as a compact struct: feature_id, threshold (quantized), left_idx, right_idx or a packed next_idx/leaf_value.- Predicate/branchless evaluation: for a vector of samples, load feature values (SoA layout) and compute cmp = feature >= threshold producing a mask; use mask to compute next node indices with SIMD integer ops rather than branching.- Level-wise traversal (SIMD on samples): process all samples at level L in one SIMD pass, compute next_indices array; repeat for tree depth D. This converts depth-first recursion to D rounds of parallel compare+scatter.- Bitset / mask propagation: keep per-sample active masks so you only process active samples; use population count / compress-store to pack active indices for next round.- Table lookup for small trees: precompute subtrees/paths as compressed LUTs (e.g., 8-bit per feature quantized -> 2^k entries) to resolve multiple levels in one memory read.- Perfectly packed decision tables (hash or multi-key LUT): treat a group of features as an index into a precomputed leaf value — trades memory for latency.

Memory layout & cache effects:- Use SoA for feature storage: contiguous memory per feature enables wide loads (AVX/NEON) and hardware prefetching. Align to cache-line boundaries.- Node arrays should be compact (use 32-bit or 16-bit indices, quantized thresholds) so hot arrays fit in L1/L2. Store frequently accessed metadata (feature_id, threshold) tightly; separate large payloads (leaf values) into another array to avoid polluting caches.- Avoid AoS per node if it causes strided accesses across SIMD lanes. Instead, have parallel arrays for feature_id[], threshold[], left[], right[] to enable unit-stride reads during batch ops.- Prefetching: software prefetch next node indices for heavy branches; use gather loads only when beneficial (gathers are higher latency).- Cache effects: deep trees increase random accesses; table lookup approaches blow up memory and may thrash caches. Trade-offs depend on depth, ensemble size, and batch size.

Practical implementation tips:- Quantize thresholds and features (8–16 bit) to enable integer SIMD and smaller LUTs.- Fuse multiple small trees into a single traversal kernel to amortize loop overhead; or traverse multiple trees in parallel per sample to increase arithmetic intensity.- Use threading + vectorization: distribute samples across threads, vectorize inner loop over samples; keep batch size large enough to saturate SIMD.- Benchmark: measure throughput (samples/sec), p99 latency, and memory bandwidth. Typical wins: branchless level-wise traversal + SoA gives 2–10x lower tail latency vs recursive per-sample traversal for large ensembles; LUT approaches can be 10–50x faster at cost of 10–100x memory.

Trade-offs:- LUTs: extreme latency gains vs exponential memory growth.- Level-wise SIMD: predictable memory, lower memory but requires more rounds = depth*passes.- Quantization: reduces memory and enables SIMD integer ops but may affect model accuracy slightly — calibrate on validation set.

Recommendation:Start by flattening trees and implementing level-wise, branchless traversal with SoA feature layout and quantized thresholds. Profile hotspots (L1/L2 misses, gather latency) and iterate: add prefetching, pack node arrays, or introduce small LUTs for top-k levels to collapse multiple comparisons into one table lookup.

MediumTechnical

38 practiced

Implement iterative postorder traversal of a binary tree using one stack (no recursion) in Python and return values in postorder. This is trickier than preorder/inorder—provide a clear algorithm and discuss edge cases like single-node and skewed trees.

Sample Answer

To perform iterative postorder (left, right, root) using a single stack, keep track of the last visited node. At each step peek the stack: if the peek has an unvisited left or right child, push the child(s) downwards; otherwise pop and visit the node. This avoids needing two stacks or modifying tree structure.

python

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

def postorder_iterative(root):
    """
    Return list of values in postorder using one stack.
    """
    if not root:
        return []

    stack = [root]
    result = []
    last_visited = None

    while stack:
        node = stack[-1]  # peek
        # If going down the tree: try to go left then right
        if (node.left and last_visited not in (node.left, node.right)) or \
           (node.right and last_visited not in (node.left, node.right) and not node.left):
            # prefer left child first
            if node.left:
                stack.append(node.left)
            elif node.right:
                stack.append(node.right)
        else:
            # children already processed or absent -> visit node
            stack.pop()
            result.append(node.val)
            last_visited = node

    return result

Key points:- last_visited tells us whether we've already processed a child so we don't revisit.- We peek instead of popping until ready to visit.

Time complexity: O(n) — each node is pushed/popped at most once.Space complexity: O(h) where h is tree height (stack).

Edge cases:- Empty tree -> [] returned.- Single-node tree -> [root.val] (stack push, then pop).- Left- or right-skewed tree -> behaves like depth-first stack; stack grows to O(n).- Trees with only one child per node handled because checks consider missing left/right.

Alternative: two-stack method is simpler but uses O(n) extra space; recursion is simpler but not allowed here.

EasyTechnical

28 practiced

Implement a function `shortest_path(graph, start, goal)` in Python where `graph` is an adjacency-list dict mapping node ids to lists of neighbor ids. Return the shortest path as a list of nodes (including start and goal) or `None` if unreachable. Constraints: O(V+E) time, O(V) extra memory. Handle empty graphs and start==goal.

Sample Answer

Use BFS to find the shortest unweighted path. BFS explores level-by-level and lets you reconstruct the path by storing each node’s predecessor. This yields O(V+E) time and O(V) extra memory (visited + predecessor map).

python

from collections import deque

def shortest_path(graph, start, goal):
    """
    graph: dict[node] -> list[neighbor]
    returns: list of nodes from start to goal (inclusive) or None if unreachable
    """
    if start == goal:
        return [start]
    if not graph:
        return None

    visited = set([start])
    parent = {}  # child -> parent
    q = deque([start])

    while q:
        node = q.popleft()
        for nbr in graph.get(node, []):
            if nbr not in visited:
                visited.add(nbr)
                parent[nbr] = node
                if nbr == goal:
                    # reconstruct path
                    path = [goal]
                    while path[-1] != start:
                        path.append(parent[path[-1]])
                    return list(reversed(path))
                q.append(nbr)
    return None

Key points:- BFS guarantees shortest path length in unweighted graphs.- parent map reconstructs the path in O(path length) time.Time Complexity: O(V + E). Space Complexity: O(V) for visited, parent, and queue.

Edge cases:- Empty graph: returns None.- start == goal: returns [start].- Nodes not present as keys: graph.get(node, []) handles missing entries.- Disconnected graph: returns None.

MediumTechnical

30 practiced

Implement an iterative DFS in Python to check whether there exists a path between two nodes in a directed graph. Use early exit to improve performance, handle missing nodes gracefully, and discuss stack size and worst-case complexity.

Sample Answer

To check path existence using iterative DFS, use an explicit stack and a visited set, return immediately when target found (early exit), and handle missing nodes by returning False. Iterative DFS avoids Python recursion limits and is appropriate in production ML pipelines.

python

def has_path_iterative_dfs(graph, start, target):
    """
    graph: dict[node] -> iterable of neighbors (directed)
    start, target: nodes (any hashable)
    Returns True if there's a path start -> target, else False.
    """
    if start == target:
        return start in graph or start is not None  # handle trivial case

    # If start or target absent in graph keys and not present as isolated nodes in values:
    if start not in graph:
        return False

    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node == target:
            return True  # early exit on discovery
        if node in visited:
            continue
        visited.add(node)
        # push neighbors; converting to list ensures deterministic order if needed
        for nbr in graph.get(node, []):
            if nbr not in visited:
                stack.append(nbr)
    return False

Key points:- Iterative DFS uses O(V + E) time in worst case; each node and edge processed once.- Space: O(V) for visited + O(V) stack in worst case (graph is a long chain).- Stack size equals maximum depth of explored path; iterative approach avoids call-stack recursion limits.- Early exit often much faster when target reachable near start.- Edge cases: missing start/target, empty graph, self-loop (start==target), graphs with nodes only appearing as neighbors (ensure graph contains such nodes if necessary).

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.