Trees and Graphs Questions

Comprehensive knowledge of tree and graph data structures and algorithms commonly tested in coding interviews. Candidates should understand representations such as adjacency list and adjacency matrix and when to use each, and tree representations including n ary trees and binary search trees. Expect to implement and reason about traversals including depth first search and breadth first search, tree traversals such as pre order in order and post order, and level order traversal. Cover algorithms including topological sorting for directed acyclic graphs, cycle detection, connected components, shortest path algorithms such as breadth first search for unweighted graphs, Dijkstra for nonnegative weights, and Bellman Ford for graphs with negative edges, and minimum spanning tree algorithms such as Kruskal and Prim. Include disjoint set union find for connectivity and for use with Kruskal, lowest common ancestor techniques and implementations, tree dynamic programming problems, serialization and deserialization, reconstruction from traversals, balancing and validation checks for binary search trees and balanced tree concepts, diameter and path sum problems, and common interview patterns such as path finding dependency resolution and structural transformation. Emphasize implementation details and common pitfalls including correct use of visited tracking recursion depth edge cases and disconnected components, and practice articulating time and space complexity tradeoffs and algorithm selection under different constraints.

EasyTechnical

82 practiced

Implement two functions in Python: build_adjacency_list(edges, n) and build_adjacency_matrix(edges, n). edges is a list of tuples (u, v) for an undirected graph with nodes labeled 0..n-1. Return the adjacency list and adjacency matrix respectively. After implementing, discuss time and space complexities and describe scenarios (sparse vs dense graphs) where you would prefer one representation over the other.

Sample Answer

To implement these, use a list of lists (or lists of sets) for adjacency list and a 2D list for adjacency matrix.

python

def build_adjacency_list(edges, n):
    """
    edges: list of (u, v) undirected edges, nodes 0..n-1
    returns: adjacency list as list of lists
    """
    adj = [[] for _ in range(n)]
    for u, v in edges:
        # skip invalid edges if desired
        if 0 <= u < n and 0 <= v < n:
            adj[u].append(v)
            if u != v:
                adj[v].append(u)
    return adj

def build_adjacency_matrix(edges, n):
    """
    returns: n x n adjacency matrix (0/1 integers)
    """
    mat = [[0] * n for _ in range(n)]
    for u, v in edges:
        if 0 <= u < n and 0 <= v < n:
            mat[u][v] = 1
            mat[v][u] = 1  # undirected
    return mat

Key points:- Adjacency list: O(n + m) time to build (m = number of edges), space O(n + m).- Adjacency matrix: O(n^2 + m) time to set entries (but dominated by n^2 for allocation), space O(n^2).- Use list-of-sets if you need O(1) remove/check of neighbors and to avoid duplicate entries.- Prefer adjacency list for sparse graphs (m << n^2) — faster neighbor iteration and much less memory.- Prefer adjacency matrix for dense graphs or when you need O(1) edge-existence queries or use algorithms relying on matrix ops (e.g., some spectral methods).

Edge cases:- Self-loops handled (mat[u][u]=1; list will include u twice unless guarded).- Invalid node indices are ignored in this implementation; you could raise exceptions instead.

MediumTechnical

86 practiced

Implement computation of strongly connected components (SCCs) for a directed graph using either Kosaraju or Tarjan algorithm in Python. Return a list of SCCs (each SCC as a list of nodes). Explain algorithmic tradeoffs and why Tarjan finds SCCs in one DFS while Kosaraju uses two passes.

Sample Answer

To compute SCCs efficiently I’ll use Tarjan’s algorithm (single DFS, O(V+E)). Tarjan maintains a discovery index, lowlink per node, and a stack of current DFS path; when node.index == node.lowlink we pop the stack to form an SCC.

python

def tarjan_scc(graph):
    """
    graph: dict[node] -> list[neighbor]
    returns: list of SCCs, each SCC is a list of nodes
    """
    index = {}          # discovery index
    lowlink = {}
    stack = []
    onstack = set()
    sccs = []
    idx = 0

    def dfs(v):
        nonlocal idx
        index[v] = idx
        lowlink[v] = idx
        idx += 1
        stack.append(v)
        onstack.add(v)

        for w in graph.get(v, []):
            if w not in index:
                dfs(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in onstack:
                lowlink[v] = min(lowlink[v], index[w])

        if lowlink[v] == index[v]:
            comp = []
            while True:
                w = stack.pop()
                onstack.remove(w)
                comp.append(w)
                if w == v:
                    break
            sccs.append(comp)

    for node in graph:
        if node not in index:
            dfs(node)
    return sccs

Key points:- Time: O(V+E). Space: O(V) for stacks and arrays.- Tarjan finds SCCs in one DFS by tracking lowlink (earliest reachable ancestor in DFS tree). When a node’s lowlink equals its index, no back-edge reaches an earlier node outside the current stack, so that node is a root of an SCC.- Kosaraju uses two passes: first DFS to compute finish order, reverse graph, then DFS in that order to extract SCCs. Tradeoffs: Kosaraju is simpler conceptually and easier to implement (requires explicit graph reversal) but needs two passes and extra memory for reversed graph; Tarjan is faster in practice (single pass, no graph reversal) but slightly trickier to implement and reason about.Edge cases: disconnected nodes, self-loops, nodes with no outgoing edges, non-hashable node ids (use integers/strings).

EasyTechnical

71 practiced

Explain when to use adjacency matrix versus adjacency list representations for graphs. For each representation, describe memory usage and time complexity for operations: checking edge existence, iterating neighbors, and adding/removing edges. Give ML-related examples where a dense matrix is preferable (e.g., spectral methods) and where adjacency list is preferable (e.g., sparse GNNs).

Sample Answer

Short answer: use an adjacency matrix when the graph is dense or when you need fast constant-time edge queries and linear-algebra-friendly operations; use an adjacency list when the graph is sparse and you need memory efficiency and fast neighbor iteration.

Definitions & memory:- Adjacency matrix: n × n matrix, memory O(n^2).- Adjacency list: array/list per node storing neighbors, memory O(n + m) where m = number of edges.

Operation costs (n nodes, m edges, deg(u) degree of u):- Check edge existence: - Matrix: O(1) — direct lookup A[u][v]. - List: O(deg(u)) — search u’s neighbor list (can be O(1) with a hash set at extra cost).- Iterate neighbors of u: - Matrix: O(n) — scan row u (wastes time if sparse). - List: O(deg(u)) — optimal for sparse graphs.- Add edge (directed): - Matrix: O(1) — set A[u][v] = 1. - List: O(1) amortized to append; removing an edge is O(deg(u)) unless using hashed containers.- Remove edge: - Matrix: O(1). - List: O(deg(u)) to find and remove (or O(1) with hash-based neighbor sets).

ML-related examples / when to prefer each:- Prefer dense adjacency matrix: - Spectral methods (eigen-decomposition, Laplacian-based clustering, graph Fourier transforms) where you perform matrix operations (L = D−A) and benefit from dense linear algebra or GPUs. - Small-to-medium fully-connected similarity graphs (e.g., pairwise kernel matrices, attention-like dense interactions) where n is modest and dense ops are efficient. - Some graph signal-processing algorithms that require matrix multiplications or eigensolvers.- Prefer adjacency list (or sparse matrix formats like CSR/COO): - Large-scale GNNs and message-passing on real-world graphs (social networks, citation graphs, recommender-system interaction graphs) that are very sparse — lower memory and faster neighbor iteration. - Production pipelines with billion-edge graphs where O(n^2) is infeasible. - Mini-batching neighbor sampling in GNN training where iterating actual neighbors quickly is critical.

Practical note: use sparse matrix libraries (CSR/COO) as a middle ground for ML — they allow efficient linear-algebra on sparse graphs and integrate with frameworks (PyTorch sparse, SciPy) for many spectral and GNN workloads.

EasyTechnical

70 practiced

Implement has_cycle_undirected(n, edges) in Python to detect if an undirected graph with nodes 0..n-1 contains a cycle. Use adjacency list and a DFS recursion approach. Your implementation must correctly handle disconnected components and avoid false positives due to the immediate parent edge.

Sample Answer

Approach: Build an adjacency list, then run DFS from every unvisited node. During recursion, pass the parent node and treat an already-visited neighbor as a cycle only if it's not the parent (to avoid the immediate parent edge false positive). This handles disconnected components.

python

def has_cycle_undirected(n, edges):
    """
    Detect cycle in an undirected graph with nodes 0..n-1 using DFS recursion.
    Returns True if any cycle exists, False otherwise.
    """
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                # visited and not the immediate parent => cycle
                return True
        return False

    # Handle disconnected components
    for i in range(n):
        if not visited[i]:
            if dfs(i, -1):
                return True
    return False

Key points:- parent argument avoids treating the bidirectional edge back to caller as a cycle.- We start DFS from each unvisited node to cover disconnected graphs.

Time Complexity: O(n + m) where m = number of edges.Space Complexity: O(n + m) for adjacency list + O(n) recursion stack in worst case.

Edge cases:- n = 0 or no edges -> False- Self-loops (u == v) should be treated as cycles if present; current code will detect them because v == u and visited[u] is True -> counts as v != parent (parent differs), so if needed explicitly handle self-loops by checking u==v when building edges.

MediumTechnical

83 practiced

Given an undirected weighted tree with n nodes and edge list (u, v, w), implement compute_tree_diameter(n, edges) in Python using two BFS/DFS passes (or appropriate weighted variant) and return both the diameter length and the sequence of nodes on that diameter path. Explain why two passes suffice on trees.

Sample Answer

Approach: For weighted trees, two DFS/BFS passes suffice. Start from any node, run a weighted DFS to find the farthest node A (by distance). From A run another DFS that records parents and distances; the farthest node B gives the diameter length and parent pointers reconstruct the path A→B. Reason: in a tree, the farthest node from any node is an endpoint of some diameter; repeating from that endpoint finds the opposite endpoint.

python

from collections import defaultdict, deque

def compute_tree_diameter(n, edges):
    """
    n: number of nodes (1..n)
    edges: list of (u, v, w) undirected weighted edges
    Returns: (diameter_length, path_nodes_list)
    """
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))

    def farthest(start):
        # weighted DFS using stack: returns (farthest_node, dist_map, parent_map)
        dist = {start: 0}
        parent = {start: None}
        stack = [start]
        while stack:
            u = stack.pop()
            for v, w in g[u]:
                if v not in dist:
                    dist[v] = dist[u] + w
                    parent[v] = u
                    stack.append(v)
        # find farthest
        far_node = max(dist, key=lambda x: dist[x])
        return far_node, dist, parent

    if n == 0:
        return 0, []
    # pass 1: from arbitrary node 1 (or any present node)
    any_node = next(iter(g)) if g else 1
    A, _, _ = farthest(any_node)
    # pass 2: from A to get B and parents
    B, dist, parent = farthest(A)
    diameter_length = dist[B]
    # reconstruct path A -> B
    path = []
    cur = B
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return diameter_length, path

Key points:- Time: O(n) since each DFS visits each edge once; Space: O(n).- Edge cases: single node, disconnected input (not a tree) — function assumes valid tree.

Unlock Full Question Bank

Get access to hundreds of Trees and Graphs interview questions and detailed answers.

Join thousands of developers preparing for their dream job.