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.

MediumTechnical

27 practiced

Given preorder and inorder traversal arrays of a binary tree with unique values, implement buildTree(preorder, inorder) in C++ that reconstructs the binary tree and returns its root. Discuss time and space complexity and how to optimize lookups to O(1) using auxiliary data structures.

Sample Answer

Approach:Use recursion: preorder gives root first; inorder splits left/right subtrees. To avoid O(n) scans per recursion, build an unordered_map from value to inorder index for O(1) lookups.

cpp

#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    unordered_map<int,int> idx; // value -> inorder index
    vector<int> pre;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre = preorder;
        int n = preorder.size();
        for (int i = 0; i < (int)inorder.size(); ++i) idx[inorder[i]] = i;
        return build(0, n-1, 0, n-1);
    }
private:
    // preorder range: preL..preR, inorder range: inL..inR
    TreeNode* build(int preL, int preR, int inL, int inR) {
        if (preL > preR || inL > inR) return nullptr;
        int rootVal = pre[preL];
        TreeNode* root = new TreeNode(rootVal);
        int inRoot = idx[rootVal];
        int leftSize = inRoot - inL;
        root->left = build(preL + 1, preL + leftSize, inL, inRoot - 1);
        root->right = build(preL + leftSize + 1, preR, inRoot + 1, inR);
        return root;
    }
};

Key points:- Use preorder[preL] as root; locate it in inorder via hashmap to split.- Recurse with correct index arithmetic for left/right subtree sizes.

Time complexity: O(n) — each node processed once, O(1) lookup via hashmap.Space complexity: O(n) extra for hashmap + O(h) recursion stack (h = tree height), worst-case O(n).Edge cases: empty inputs, mismatched sizes, unique values assumption (required for mapping).

MediumTechnical

57 practiced

Implement stronglyConnectedComponents(graph) in Java to compute all strongly connected components (SCCs) for a directed graph. You may use Kosaraju's or Tarjan's algorithm—choose one and justify your choice. Explain complexity, memory trade-offs, and how to validate correctness on graphs with many small SCCs.

Sample Answer

I choose Tarjan's algorithm because it finds SCCs in a single DFS pass (O(V+E) time) and uses O(V) extra stack/arrays; it's simpler to implement in one pass and slightly better when graph transpose is expensive or implicit.

Approach summary:1. Run DFS, assign each node an index and lowlink.2. Use a stack to collect nodes of the current SCC.3. When node.index == node.lowlink, pop stack to generate an SCC.

java

import java.util.*;

public class SCC {
    // graph: adjacency list map node -> neighbors
    public static List<List<Integer>> stronglyConnectedComponents(Map<Integer, List<Integer>> graph) {
        int n = graph.size();
        Map<Integer, Integer> indexMap = new HashMap<>();
        Map<Integer, Integer> lowlink = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        Set<Integer> onStack = new HashSet<>();
        List<List<Integer>> result = new ArrayList<>();
        int[] idx = {0}; // mutable counter

        for (Integer v : graph.keySet()) {
            if (!indexMap.containsKey(v)) dfs(v, graph, indexMap, lowlink, stack, onStack, result, idx);
        }
        return result;
    }

    private static void dfs(Integer v, Map<Integer, List<Integer>> graph,
                            Map<Integer, Integer> indexMap, Map<Integer, Integer> lowlink,
                            Deque<Integer> stack, Set<Integer> onStack,
                            List<List<Integer>> result, int[] idx) {
        indexMap.put(v, idx[0]);
        lowlink.put(v, idx[0]);
        idx[0]++;
        stack.push(v);
        onStack.add(v);

        for (Integer w : graph.getOrDefault(v, Collections.emptyList())) {
            if (!indexMap.containsKey(w)) {
                dfs(w, graph, indexMap, lowlink, stack, onStack, result, idx);
                lowlink.put(v, Math.min(lowlink.get(v), lowlink.get(w)));
            } else if (onStack.contains(w)) {
                lowlink.put(v, Math.min(lowlink.get(v), indexMap.get(w)));
            }
        }

        if (lowlink.get(v).equals(indexMap.get(v))) {
            List<Integer> scc = new ArrayList<>();
            Integer w;
            do {
                w = stack.pop();
                onStack.remove(w);
                scc.add(w);
            } while (!w.equals(v));
            result.add(scc);
        }
    }
}

Key points:- Time complexity: O(V + E) — each edge and vertex processed once.- Space complexity: O(V) for index/lowlink/stack + recursion stack (O(V) worst-case).- Trade-offs vs Kosaraju: Kosaraju needs two passes and explicit graph transpose or extra memory for reversed edges (extra O(E) memory or time to build transpose). Tarjan is single-pass and memory-efficient when transpose is costly.

Edge cases:- Empty graph, isolated vertices (SCCs of size 1), self-loops (count as size-1 SCC with self).- Graph nodes not 0..n-1 — used Map to support arbitrary labels.

Validation on graphs with many small SCCs:- Unit tests generating worst-case patterns: many isolated nodes, many tiny cycles (e.g., 2-node cycles repeated).- Check invariants: union of all SCC node sets equals node set; SCCs are disjoint; for each SCC, there are no edges from node A to node B and back unless within same SCC — or verify condensation graph is a DAG.- Fuzz tests: random graphs with known SCCs via alternative algorithm (Kosaraju) to cross-validate outputs. Also assert total nodes counted equals graph.size().

EasyTechnical

37 practiced

Explain the formal differences between a tree and a general graph. Describe properties that define a tree (connected, acyclic, exactly n-1 edges for n nodes), implications such as unique simple path between nodes, and how those properties simplify algorithms (e.g., no need for visited set in some traversals). Give concrete examples of when you'd model a problem as a tree versus as a general graph.

EasyTechnical

38 practiced

Write a Python function count_components(n, edges) that returns the number of connected components in an undirected graph with n nodes labeled 0..n-1 given an edge list. Implement using DFS (iterative or recursive) and ensure isolated nodes are counted. State time and space complexity and behavior for very sparse graphs.

Sample Answer

Approach: Build an adjacency list, then run DFS (iterative stack) from each unvisited node; each DFS explores one connected component. Isolated nodes (no edges) are visited as single-node components.

python

def count_components(n, edges):
    """
    Count connected components in an undirected graph with nodes 0..n-1.
    Uses iterative DFS to avoid recursion depth issues.
    """
    if n <= 0:
        return 0

    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        if 0 <= u < n and 0 <= v < n:
            adj[u].append(v)
            if u != v:           # avoid double-adding self-loop
                adj[v].append(u)

    visited = [False] * n
    components = 0

    for node in range(n):
        if not visited[node]:
            components += 1
            # iterative DFS
            stack = [node]
            visited[node] = True
            while stack:
                cur = stack.pop()
                for nei in adj[cur]:
                    if not visited[nei]:
                        visited[nei] = True
                        stack.append(nei)
    return components

Key points:- Time complexity: O(n + m) where m = number of edges (building adjacency + visiting once).- Space complexity: O(n + m) for adjacency list and O(n) for visited/stack.- For very sparse graphs (m << n) runtime is dominated by O(n) — building adjacency is O(n) and DFS touches each isolated node once, so it's efficient.- Handles isolated nodes, duplicate edges, and self-loops (self-loops don't inflate component count). Edge-case: invalid edge endpoints are ignored; for n=0 returns 0.

HardTechnical

59 practiced

Implement Bellman-Ford in C++ to compute single-source shortest paths on graphs that may have negative edge weights but no negative cycles. Detect negative cycles and explain practical optimizations and alternatives (SPFA heuristics, Johnson's algorithm for all-pairs) when V*E complexity is prohibitive for large graphs.

Sample Answer

Approach: Use Bellman-Ford on an edge list: relax all edges V-1 times to get shortest distances, then run one more pass to detect any negative cycle (an edge that can still relax indicates a negative cycle). Practical optimizations: early stopping when no distance changes, process only reachable vertices/edges, and for all-pairs use Johnson (reweight + Dijkstra). SPFA (queue-based) often faster in practice but can degrade to O(VE) and needs heuristics (small label first, SLF/LLL) and cycle detection.

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

struct Edge { int u,v; ll w; };

pair<vector<ll>, bool> bellman_ford(int V, const vector<Edge>& edges, int src) {
    vector<ll> dist(V, INF);
    dist[src]=0;
    // Relax V-1 times
    for(int i=0;i<V-1;i++){
        bool changed=false;
        for(const auto &e: edges){
            if(dist[e.u]==INF) continue;
            if(dist[e.u]+e.w < dist[e.v]){
                dist[e.v]=dist[e.u]+e.w;
                changed=true;
            }
        }
        if(!changed) break; // early stop optimization
    }
    // Check for negative cycle
    for(const auto &e: edges){
        if(dist[e.u]==INF) continue;
        if(dist[e.u]+e.w < dist[e.v]){
            return {dist, true}; // negative cycle reachable
        }
    }
    return {dist, false};
}

Key points:- Time: O(V*E) worst-case; Space: O(V+E).- Edge cases: disconnected graphs (use INF), large weights (use ll and overflow care), source unreachable nodes.- Alternatives: SPFA with SLF/LLL heuristics and visited counts to detect negative cycles in practice; Johnson's algorithm for all-pairs (run Bellman-Ford once to get potentials, reweight edges to non-negative, then run Dijkstra from each vertex) gives O(V E + V^2 log V) depending on implementation — far faster when many sparse Dijkstra runs are cheaper than repeated relaxations.

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.