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

59 practiced

Explain and implement the Bellman-Ford algorithm in Python to compute shortest paths from a source in a graph that may contain negative edge weights. Signature: def bellman_ford(edges: List[Tuple[int,int,int]], n: int, source: int) -> Tuple[List[float], bool] where the boolean indicates whether a negative-weight cycle is present. Discuss why Bellman-Ford is O(VE) and when it's necessary over Dijkstra.

Sample Answer

**Approach (brief)** Bellman-Ford relaxes all edges V-1 times to find shortest paths in graphs with negative weights and then does one more pass to detect negative cycles.

**Python implementation**

python

from typing import List, Tuple
import math

def bellman_ford(edges: List[Tuple[int,int,int]], n: int, source: int) -> Tuple[List[float], bool]:
    # distances initialized to +inf, source = 0
    dist = [math.inf] * n
    dist[source] = 0.0

    # Relax edges up to n-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != math.inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # early stop if no change

    # Check for negative-weight cycle
    neg_cycle = False
    for u, v, w in edges:
        if dist[u] != math.inf and dist[u] + w < dist[v]:
            neg_cycle = True
            break

    return dist, neg_cycle

**Key concepts and reasoning**- Relaxing an edge updates a tentative shortest path. After V-1 full relaxations, any shortest path (without cycles) is found because a simple path has at most V-1 edges.- The extra pass detects edges that can still be relaxed => reachable negative cycle.

**Complexity**- Time: O(V * E) because up to V-1 iterations each scanning E edges.- Space: O(V) for distances (plus O(E) input).

**When to use over Dijkstra**- Use Bellman-Ford if edges may have negative weights or you must detect negative cycles. Dijkstra is faster (O(E + V log V)) but requires non-negative edge weights.

**Edge cases / best practices**- Handle disconnected nodes (dist remains inf). For backend services, validate inputs (0 <= node < n), and prefer early termination when no update.

MediumTechnical

60 practiced

Given preorder and inorder traversal arrays of a binary tree, implement a function in Python to reconstruct the original binary tree. Signature: def build_tree(preorder: List[int], inorder: List[int]) -> TreeNode. Discuss algorithmic complexity and edge cases such as mismatched input sizes or repeated values.

Sample Answer

**Approach (brief)** Use preorder to pick root (first element). Find root index in inorder to split left/right subtrees. Recurse, using indices to avoid slicing overhead and a hashmap for inorder positions to get O(1) lookups.

python

from typing import List, Optional

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

def build_tree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if len(preorder) != len(inorder):
        raise ValueError("Preorder and inorder must have same length")
    n = len(preorder)
    idx_map = {v:i for i,v in enumerate(inorder)}  # assumes unique values; see edge cases
    pre_index = 0

    def helper(in_l:int, in_r:int):
        nonlocal pre_index
        if in_l > in_r: 
            return None
        root_val = preorder[pre_index]
        pre_index += 1
        if root_val not in idx_map:
            raise ValueError("Value in preorder not found in inorder")
        mid = idx_map[root_val]
        node = TreeNode(root_val)
        node.left = helper(in_l, mid-1)
        node.right = helper(mid+1, in_r)
        return node

    return helper(0, n-1)

**Complexity** - Time: O(n) with hashmap lookups and each node constructed once. - Space: O(n) for hashmap + recursion stack up to O(n) worst-case.

**Edge cases & notes** - Mismatched sizes or missing values -> raise error. - Repeated values: above approach requires unique values. For duplicates, use inorder positions mapped to lists/queues and pop positions in order of appearance or augment nodes with unique IDs. - Empty arrays -> return None.

As a backend developer, prefer index-based recursion to avoid excessive allocations and ensure predictable performance in production.

EasyTechnical

75 practiced

Implement a Union-Find (Disjoint Set Union) data structure in C++ with path compression and union by rank. Provide functions: int find(int x) and void unite(int x, int y). Explain time complexity for m operations on n elements and describe a backend use-case where union-find is preferable to repeated DFS/BFS.

Sample Answer

**Approach (brief)**Use parent[] and rank[] arrays. find() uses path compression (point nodes directly to root). unite() uses union by rank to attach smaller tree beneath larger.

**C++ implementation**

cpp

#include <vector>
struct DSU {
    std::vector<int> parent, rank;
    DSU(int n): parent(n), rank(n,0) { for(int i=0;i<n;++i) parent[i]=i; }
    int find(int x){
        if(parent[x]==x) return x;
        return parent[x] = find(parent[x]); // path compression
    }
    void unite(int x, int y){
        int rx = find(x), ry = find(y);
        if(rx==ry) return;
        if(rank[rx] < rank[ry]) parent[rx] = ry;
        else if(rank[ry] < rank[rx]) parent[ry] = rx;
        else { parent[ry]=rx; rank[rx]++; }
    }
};

**Complexity**For n elements and m operations, amortized time per operation is α(n) (inverse Ackermann). So m operations cost O(m α(n)) ~ effectively linear.

**Backend use-case**Use DSU for dynamic connectivity (e.g., merging accounts, feature-flag groups, or building MSTs for service network). Prefer DSU over repeated DFS/BFS when you need many incremental union/find queries: DSU handles online unions/finds in near-constant time, while DFS/BFS from scratch each query is O(n+e) and costly for frequent checks.

EasyTechnical

72 practiced

Explain the main practical differences between BFS and DFS in terms of order of visiting nodes, memory patterns, and when one is preferred over the other for backend tasks such as computing shortest unweighted paths, exploring configuration graphs, or performing garbage collection/traversal.

HardSystem Design

85 practiced

Design a graph query service (system design) to compute shortest-path queries on a continental road network for a backend API used by routing clients. Requirements: low-latency queries (under 200ms), support many concurrent queries, memory budget on each machine limited to a few GBs, ability to update edge weights periodically (traffic updates). Describe high-level architecture, partitioning/sharding strategy, preprocessing (e.g., contraction hierarchies, landmarks), caching, fallback strategies, and how you would measure and test performance.

Sample Answer

**Clarify requirements & constraints**- Target: shortest-path queries <200ms per query for continental road graph, many concurrent queries, per-node memory a few GB, periodic edge-weight updates (traffic).

**High-level architecture**- Frontend API layer (load balancers) → Query routers → Sharded routing workers (in-memory indexes) → Persistent graph store (object storage + DB for updates).- Use autoscaling groups behind LB; health checks and circuit breakers.

**Partitioning / sharding**- Spatial partitioning by geographic tiles (e.g., S2/H3) with overlap buffers at borders.- Assign tiles to workers; cross-tile queries routed to multiple workers or a coordinator that stitches partial results.- Hash by origin tile for affinity and cache locality.

**Preprocessing**- Use Contraction Hierarchies (CH) per tile and across border edges; store upward/downward graphs to enable fast queries.- Augment with Landmark (ALT) heuristics for A* pruning when CH alone is heavy.- Precompute boundary vertex shortcuts and multi-level CH to limit memory.

**Caching**- LRU per-node result cache for popular O-D pairs and route segments.- Edge-weight delta cache: keep base static CH plus small dynamic overlay of traffic deltas applied at query time.- CDN-like cache for long routes and directions.

**Updates & consistency**- Periodic weight updates: apply as incremental overlays of deltas; rebuild local CH asynchronously per tile during low-traffic windows.- Use versioning: queries tag index version; gradual rollouts and blue/green swap of rebuilt indexes.

**Fallbacks & correctness**- If CH index stale or insufficient, fallback to bidirectional Dijkstra limited to a radius or to simpler A* on compressed graph; accept higher latency but maintain correctness.- Return partial route with ETA estimate if full compute times out.

**Measurement & testing**- Metrics: p95/p99 latency, QPS, CPU/memory per worker, cache hit ratio, route divergence from baseline optimality.- Tests: synthetic load (varying origin/destination distributions), chaos tests during index swaps, A/B on live traffic, unit tests for stitching correctness.- Benchmarks: replay real query logs, inject traffic updates, measure rebuild time and query-impact window.

**Trade-offs**- CH gives microsecond queries but heavier rebuilds; overlay deltas reduce rebuild frequency at cost of slightly worse pruning.- Spatial tiles reduce memory but require careful border handling.

This design prioritizes sub-200ms latency, bounded memory per machine, and practical update paths for traffic-weight changes while allowing graceful degradation.

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.