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.

MediumTechnical

84 practiced

Given specific numeric values for n (nodes) and m (edges), analyze when an adjacency list vs adjacency matrix is more appropriate. For example, for n = 100k and m = 1M, compute approximate memory requirements and operation costs for edge lookup and neighbor iteration; discuss bitset optimizations and sparse matrix libraries.

Sample Answer

Start by clarifying assumptions: store 32-bit node IDs (4 bytes). Consider directed graphs unless stated otherwise (undirected doubles stored edges). We'll compare a typical adjacency list, a dense adjacency matrix (as bytes), and a bitset-per-row matrix; then mention sparse-matrix formats.

Memory estimates (n = 100,000; m = 1,000,000):- Adjacency list (vector<int> per neighbor, contiguous edge array): edges store m ints = 1,000,000 × 4B = 4 MB. Per-vertex index/offset array = n × 4B = 400 KB. Real-world overhead (vector headers, pointers, allocator fragmentation, language GC) pushes this higher; rough practical footprint ~10–50 MB depending on language/implementation. For undirected, double to ~8 MB raw.- Adjacency matrix (byte per entry): n² entries = 100k² = 10^10 bytes ≈ 10 GB. Not feasible in RAM for most apps.- Bitset adjacency matrix (1 bit per pair): 10^10 bits = 1.25 × 10^9 bytes ≈ 1.25 GB. This is feasible on large-memory machines but still large.- Sparse matrix (CSR/CSC): store two arrays: indices (m ints = 4 MB) and offsets (n+1 ints ≈ 400 KB), plus values if needed. Memory similar to adjacency list (~5 MB), with low overhead.

Operation costs:- Neighbor iteration for a node u: - Adjacency list: O(deg(u)) — optimal when graph is sparse. For average degree = 2m/n = 20, iteration is ~20 steps. - Adjacency matrix (byte/bitset): O(n) to scan a row (100k tests) unless bit-level scans with fast word operations; still much more work than list iteration when deg(u) ≪ n.- Edge lookup (is (u,v) present?): - Adjacency list: O(deg(u)) if you scan the list, or O(1) average if you store a hash set per vertex (but that increases memory). - Adjacency matrix: O(1) direct index lookup (very fast). - Bitset row: O(1) via bit test (very cache-friendly if row is memory-contiguous).

Bitset optimizations:- Bitsets compress adjacency to 1 bit/edge presence and support fast bitwise operations (AND/OR) for intersection queries (common-neighbor, triangle counting) and fast row scans using word-level popcount. A 1.25 GB bitset matrix allows extremely fast algebraic operations and GPU/parallel acceleration.- Trade-offs: bitsets are dense per-row (fixed cost per row regardless of deg), so wasteful when graph is sparse and n large.

Sparse-matrix libraries and formats:- CSR/CSC (Compressed Sparse Row/Column) store only existing edges and support extremely efficient matrix-vector multiply and many graph algorithms (PageRank, BFS in linear algebra style). Libraries: SuiteSparse, Eigen (sparse), SciPy.sparse, MKL sparse, GraphBLAS implementations.- Advantages: low memory, fast for linear-algebra style ops; disadvantage: costly random edge insertion/removal (requires rebuild or indirection).

Recommendation for n=100k, m=1M:- Use adjacency list or CSR for general graph algorithms and typical software engineering tasks — minimal memory (~few MBs) and excellent neighbor iteration performance.- If you need extremely fast O(1) edge existence checks and can afford ~1.25 GB, use bitset rows.- If you run heavy linear-algebraic graph algorithms (PageRank, spectral methods) prefer sparse-matrix libraries (CSR) or GraphBLAS for optimized kernels.- If you need both fast lookup and low memory, consider hybrid: adjacency lists for iteration, and per-high-degree-node bitset or hash set for O(1) lookups.

Practical note: language matters — C/C++ will achieve lower overhead; Java/Python add significant per-object cost, so prefer contiguous arrays or specialized libs (e.g., array-backed lists, scipy.sparse).

HardTechnical

59 practiced

Given a directed acyclic graph (DAG) representing tasks with durations and precedence constraints, design an algorithm to compute the earliest completion time for each task and the overall project completion time. Explain how topological ordering and the critical path method are combined and how to modify the algorithm when resources are constrained (limited parallel workers).

Sample Answer

Approach (brief): compute earliest start (ES) and earliest finish (EF) times using a topological order and longest-path DP (this is the forward pass of the Critical Path Method). Overall project completion = max(EF). For resource constraints (limited workers) apply list-scheduling: process tasks by ES priority, but only start up to W tasks at a time; break ties by smallest slack (or largest EF) to approximate criticality; for optimal under resource constraints the problem becomes NP-hard (resource-constrained project scheduling), so heuristics or integer programming are used.

Algorithm (forward pass + simple list-scheduler):

1. Topologically sort DAG (Kahn).2. Initialize ES[task]=0.3. For node u in topo order: - EF[u] = ES[u] + dur[u] - For each v in out[u]: ES[v] = max(ES[v], EF[u])4. Project completion = max_u EF[u]

To add resource limit W (greedy list-scheduling):- Build event timeline. Maintain ready set = tasks with all preds done.- At each time t, while workers < W and ready non-empty: pick task with highest priority (e.g., smallest slack = LFT−ES or largest duration/EarliestFinish), start it; advance time to next completion, free workers, add newly ready tasks, repeat.

Python sketch:

python

from collections import deque, defaultdict
def earliest_times(nodes, edges, dur):
    indeg=defaultdict(int); out=defaultdict(list)
    for u,v in edges:
        out[u].append(v); indeg[v]+=1
    q=deque([n for n in nodes if indeg[n]==0])
    topo=[]; ES={n:0 for n in nodes}
    while q:
        u=q.popleft(); topo.append(u)
        EF=ES[u]+dur[u]
        for v in out[u]:
            ES[v]=max(ES[v],EF); indeg[v]-=1
            if indeg[v]==0: q.append(v)
    EF={u:ES[u]+dur[u] for u in nodes}
    return ES, EF, max(EF.values())

Complexity: topological + DP O(V+E). List scheduling simulation is O((V+E) log V) if using priority queue. Edge cases: cycles (detect during topo), zero-duration tasks, multiple start nodes, precedence with shared successors. For exact resource-constrained optimality use CP-SAT or ILP.

MediumTechnical

64 practiced

Compute the diameter (longest path length in edges or weights) of a binary tree. Provide an O(n) algorithm and implement it; discuss how to adapt for weighted trees and how to reconstruct the actual longest path nodes, not just its length.

Sample Answer

Approach: perform one DFS that returns for each node the height (max distance downwards) and updates a global best diameter. For unweighted tree heights are counts of edges; for weighted, heights are max sum of edge weights. To reconstruct the path, store for each node the child contributing to its max height; when updating global diameter, record the two endpoints using those child links and then stitch paths.

python

# python
class Node:
    def __init__(self, val, left=None, right=None, w_left=1, w_right=1):
        self.val = val
        self.left = left
        self.right = right
        # weights for edges to children (1 for unweighted)
        self.w_left = w_left
        self.w_right = w_right

def tree_diameter(root):
    best = {'length':0, 'endpoints': (None,None), 'via': None}
    parent_choice = {}  # node -> child chosen for max height

    def dfs(node):
        if not node: 
            return 0, []  # height, path down (list of nodes from node down)
        lh, lpath = dfs(node.left)
        rh, rpath = dfs(node.right)

        # adjust for weights
        lw = node.w_left if node.left else 0
        rw = node.w_right if node.right else 0
        left_height = (lh + lw) if node.left else 0
        right_height = (rh + rw) if node.right else 0

        # potential diameter through this node
        total = left_height + right_height
        if total > best['length']:
            best['length'] = total
            # endpoints: deepest node on left path and deepest on right path
            left_end = lpath[-1] if lpath else node
            right_end = rpath[-1] if rpath else node
            best['endpoints'] = (left_end, right_end)
            best['via'] = node

        # choose which child gives larger height to propagate upward
        if left_height >= right_height:
            parent_choice[node] = node.left
            path_down = [node] + lpath
            return left_height, path_down
        else:
            parent_choice[node] = node.right
            path_down = [node] + rpath
            return right_height, path_down

    dfs(root)

    # reconstruct path between endpoints: walk down from via to each endpoint using recorded paths
    if best['via'] is None:
        return 0, [root] if root else []
    # collect left side
    def collect_path_from(node, target_side):
        if not node:
            return []
        if target_side == 'left':
            _, lpath = dfs_collect(node.left)
            return [node] + lpath if lpath else [node]
        else:
            _, rpath = dfs_collect(node.right)
            return [node] + rpath if rpath else [node]

    # helper to return path down without recomputing global state
    def dfs_collect(node):
        if not node:
            return 0, []
        lh, lpath = dfs_collect(node.left)
        rh, rpath = dfs_collect(node.right)
        lw = node.w_left if node.left else 0
        rw = node.w_right if node.right else 0
        left_h = (lh + lw) if node.left else 0
        right_h = (rh + rw) if node.right else 0
        if left_h >= right_h:
            return left_h, [node] + lpath
        else:
            return right_h, [node] + rpath

    left_path = dfs_collect(best['via'].left)[1] if best['via'].left else [best['via']]
    right_path = dfs_collect(best['via'].right)[1] if best['via'].right else [best['via']]
    # combine: left_path (reversed deepest->via), then via, then right_path (via->deepest)
    full = (list(reversed(left_path)) if left_path else []) + [best['via']] + (right_path if right_path else [])
    return best['length'], [n.val for n in full]

Key points:- Single post-order DFS: O(n) time, O(h) recursion stack.- For weighted trees use edge weights when computing heights (example uses w_left/w_right).- Reconstruct path by keeping child choices or by storing the downward path at each node (above uses small paths).Edge cases:- Empty tree, single node (diameter 0).- Negative weights: algorithm still works but be careful—may prefer picking empty path if negative; adjust to allow zero baseline.

MediumTechnical

78 practiced

Implement clone (deep copy) of an undirected graph given a reference to a node. The graph may contain cycles. Provide both BFS and DFS approaches and explain how you ensure node identity mapping and avoid infinite loops.

Sample Answer

To deep-clone an undirected graph with cycles we must (1) create exactly one cloned node per original node and (2) reuse clones when neighbors reference the same node — otherwise cycles cause infinite recursion/loops. We accomplish this with a hash map (original -> clone). Below are both BFS and DFS Python implementations and explanations.

BFS approach (iterative):

python

from collections import deque

def clone_graph_bfs(node):
    if not node:
        return None
    # map original node -> cloned node
    clones = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nbr in cur.neighbors:
            if nbr not in clones:
                clones[nbr] = Node(nbr.val)   # create clone once
                q.append(nbr)                 # schedule traversal
            clones[cur].neighbors.append(clones[nbr])  # connect clones
    return clones[node]

DFS approach (recursive):

python

def clone_graph_dfs(node, clones=None):
    if not node:
        return None
    if clones is None:
        clones = {}
    if node in clones:
        return clones[node]                # already cloned -> avoids cycles
    clones[node] = Node(node.val)          # create clone immediately
    for nbr in node.neighbors:
        clones[node].neighbors.append(clone_graph_dfs(nbr, clones))
    return clones[node]

Key points:- Use a hashmap to ensure node identity mapping and to avoid creating multiple clones for the same original node.- In BFS we create clone when first seen and push original to queue; in DFS we create clone before recursing to prevent infinite recursion on cycles.- Time: O(N + E) visiting nodes and edges once. Space: O(N) for hashmap and recursion/queue.- Edge cases: input None -> return None; disconnected components — given a starting node, only its reachable component is cloned.

EasyTechnical

104 practiced

Explain the difference between Depth-First Search (DFS) and Breadth-First Search (BFS): their typical uses, time and space complexity, order of node discovery, and real-world scenarios when you would pick one over the other (e.g., shortest unweighted paths, topological ordering, connectivity checks).

Sample Answer

Definition:- DFS (Depth-First Search) explores as far as possible along each branch before backtracking (stack/recursion).- BFS (Breadth-First Search) explores level by level from a source, visiting all neighbors at distance d before distance d+1 (queue).

Time & Space Complexity (for graph with V vertices, E edges):- Time: both O(V + E).- Space: - DFS: O(V) worst-case for recursion stack or explicit stack (O(height) for trees). - BFS: O(V) worst-case to store the frontier (can be large when a level is wide).

Order of discovery:- DFS: dives deep; discovery order follows root→child→grandchild… then backtrack. Good for exploring paths and components.- BFS: discovers nodes in increasing order of shortest-path distance (unweighted) from the source.

Typical uses / when to pick:- BFS: - Shortest path in unweighted graphs (e.g., minimum number of moves in a puzzle). - Level-order traversal, nearest-neighbor queries, shortest "degrees of separation".- DFS: - Topological sort (via post-order), cycle detection, connected components, graph traversal where you need path existence or to explore all possibilities (e.g., backtracking, maze generation). - Space advantage when graph/tree height small.

Real-world scenarios:- Use BFS to find shortest unweighted path (routing in unweighted networks, friend recommendations).- Use DFS for topological ordering of tasks (build systems), detecting cycles (deadlocks), or solving puzzles that require exploring full paths (backtracking sudoku solver).- For very large, deep graphs where stack/recursion depth is a concern, prefer iterative DFS with explicit stack or tune recursion limits; for wide graphs with many neighbors per level, BFS memory can balloon—consider bidirectional BFS for start→target shortest path.

Trade-offs summary:- BFS guarantees shortest unweighted path but can use more memory for wide frontiers.- DFS uses less average memory for narrow trees and is better for path-existence and ordering problems, but does not guarantee shortest paths.

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.