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

71 practiced

Implement a function in Python to detect a cycle in a directed graph using DFS. The graph is given as an adjacency list. Return True if any cycle exists and False otherwise. Explain why a simple visited set is insufficient for directed cycle detection and provide time/space complexity.

Sample Answer

A standard way to detect a cycle in a directed graph is to run DFS while tracking not only globally visited nodes but also the current recursion stack (nodes on the current DFS path). A node visited earlier but not on the current recursion stack doesn’t imply a cycle; only encountering a node already in the recursion stack means there is a back-edge -> cycle. Thus a single visited set is insufficient because it can't distinguish "finished" nodes from nodes on the current path.

Approach: for each unvisited node, run DFS. Maintain:- visited set: nodes fully explored (or seen)- rec_stack set: nodes currently on DFS path

If DFS reaches a neighbor in rec_stack, return True.

Example implementation:

python

def has_cycle(graph):
    """
    graph: dict[node] -> list[neighbor nodes]
    Returns True if directed cycle exists, else False.
    """
    visited = set()
    rec_stack = set()
    
    def dfs(u):
        visited.add(u)
        rec_stack.add(u)
        for v in graph.get(u, []):
            if v not in visited:
                if dfs(v):
                    return True
            elif v in rec_stack:
                return True
        rec_stack.remove(u)
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

Key points:- rec_stack detects back-edges (cycle). A plain visited set would treat any revisit as non-informative because it can be either a cross/forward edge or a back edge.- Handles disconnected graphs and self-loops (self-loop detected since neighbor==node is in rec_stack).

Time complexity: O(V + E) — each node and edge processed once.Space complexity: O(V) for visited + recursion stack (plus recursion call overhead).

EasyTechnical

80 practiced

Write a function to check whether a binary tree is height-balanced (AVL-style): for every node, heights of left and right subtrees differ by at most 1. Implement an O(n) recursive solution in Python that returns a boolean. Discuss how balancing affects tree operations in AI feature stores and decision-tree inference.

Sample Answer

Approach: do a post-order traversal that returns (is_balanced, height) for each node. If any subtree is unbalanced, propagate False. This yields O(n) time because each node is visited once.

python

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

def is_balanced(root):
    """
    Returns True if tree is height-balanced (AVL condition).
    O(n) time, O(h) recursion stack.
    """
    def helper(node):
        # returns (balanced: bool, height: int)
        if node is None:
            return True, 0
        left_bal, left_h = helper(node.left)
        if not left_bal:
            return False, 0
        right_bal, right_h = helper(node.right)
        if not right_bal:
            return False, 0
        if abs(left_h - right_h) > 1:
            return False, 0
        return True, 1 + max(left_h, right_h)

    balanced, _ = helper(root)
    return balanced

Key points:- Each node computed once -> Time O(n), Space O(h) for recursion (h = tree height).- Edge cases: empty tree -> True; skewed tree -> False when imbalance >1.- Alternative: compute heights separately causes O(n^2) in worst case; avoid that.

Relevance to AI role:- Balanced trees yield O(log n) lookups/updates; in feature stores balanced indexes (B-trees/AVL/RB) speed feature retrieval for inference pipelines and low-latency feature joins.- For decision-tree inference, balanced trees reduce worst-case path length, reducing latency and variance in prediction time; imbalance can cause hotspotting and cache inefficiency.- When training or serving many models, predictable operation costs from balanced structures improve throughput and resource planning.

HardTechnical

74 practiced

Given two nodes in a rooted tree, implement an algorithm to compute their Lowest Common Ancestor (LCA). Provide both: (1) a simple O(h) solution using parent pointers and depth, and (2) an O(1) query solution after O(n log n) preprocessing using binary lifting. Implement binary lifting preprocessing and query in Python and explain memory/time trade-offs.

Sample Answer

Approach summary:1) Simple O(h) per-query: climb the deeper node up using parent pointers until depths equal, then move both up until equal — O(h) time, O(n) space for parent/depth.2) Binary lifting: Precompute up[k][v] = 2^k-th ancestor for each node in O(n log n) time and space; then answer each LCA in O(log n) time (often called O(1) in competitive contexts per bit, but strictly O(log n) steps). If you store also entry/exit times (Euler tour + RMQ) you can get true O(1) per query after O(n) preprocessing but that's another method. Below I give binary lifting preprocessing and query in Python.

Binary lifting implementation (0-indexed nodes):

python

import math
from collections import deque

def preprocess_binary_lifting(adj, root=0):
    n = len(adj)
    LOG = math.ceil(math.log2(max(2, n)))
    up = [[-1]*n for _ in range(LOG)]   # up[k][v] = 2^k ancestor of v
    depth = [0]*n

    # BFS to set immediate parent and depth (works for large depth safely)
    q = deque([root])
    parent = [-1]*n
    parent[root] = root
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v == parent[u]:
                continue
            parent[v] = u
            depth[v] = depth[u] + 1
            q.append(v)

    # k = 0
    for v in range(n):
        up[0][v] = parent[v]

    # build table
    for k in range(1, LOG):
        for v in range(n):
            up[k][v] = up[k-1][up[k-1][v]]

    return up, depth, LOG

def lca_binary_lifting(a, b, up, depth, LOG):
    if depth[a] < depth[b]:
        a, b = b, a
    # lift a up to depth[b]
    diff = depth[a] - depth[b]
    k = 0
    while diff:
        if diff & 1:
            a = up[k][a]
        diff >>= 1
        k += 1
    if a == b:
        return a
    # lift both up from highest bit down
    for k in range(LOG-1, -1, -1):
        if up[k][a] != up[k][b]:
            a = up[k][a]
            b = up[k][b]
    return up[0][a]

Simple parent-pointer O(h) LCA:

python

def lca_simple(a, b, parent, depth):
    # lift deeper node
    while depth[a] > depth[b]:
        a = parent[a]
    while depth[b] > depth[a]:
        b = parent[b]
    while a != b:
        a = parent[a]
        b = parent[b]
    return a

Key points and trade-offs:- Preprocessing binary lifting: time O(n log n), query O(log n) (per bit shifts), memory O(n log n) for up table. Good when many queries.- Simple method: O(n) preprocessing to get parent/depth, queries O(h) (tree height). Use when few queries or memory constrained.- For very fast queries and many queries, Euler tour + RMQ (sparse table) gives O(1) queries with O(n log n) preprocessing and O(n log n) memory.- Edge cases: ensure parent[root]=root or -1 handled; disconnected graphs not allowed; LOG computed for n>=1.

This gives a production-ready binary-lifting LCA you can integrate into graph/tree pipelines for AI feature hierarchies or tree-structured model components.

MediumTechnical

85 practiced

Design and implement union-find (disjoint set union) with path compression and union by rank in Python. Provide methods: make_set(x), find(x), union(x,y). Explain amortized complexity and a scenario in AI data preprocessing where union-find accelerates operations (e.g., clustering or deduplicating connected components).

Sample Answer

To implement Disjoint Set Union (Union-Find) with path compression and union by rank, store for each element a parent and a rank (approximate tree height). make_set initializes a singleton; find follows parents and compresses path; union links roots using rank to keep trees shallow.

python

class UnionFind:
    def __init__(self):
        # parent[x] = parent of x; rank[x] = approx tree depth
        self.parent = {}
        self.rank = {}

    def make_set(self, x):
        """Create a set containing only x."""
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0

    def find(self, x):
        """Find representative (root) of x with path compression."""
        if x not in self.parent:
            raise KeyError(f"{x} not found; call make_set first")
        # iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # compress path
        while x != root:
            parent = self.parent[x]
            self.parent[x] = root
            x = parent
        return root

    def union(self, x, y):
        """Union sets containing x and y using union by rank."""
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return False  # already same set
        # attach smaller rank tree under larger rank tree
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

Key points:- Path compression flattens trees during find; union by rank attaches shorter tree under taller.- Amortized time per operation is inverse-Ackermann alpha(n) — effectively constant for any practical n. So m operations ≈ O(m α(n)).

AI data-preprocessing scenario:- Deduplicating near-duplicate records or merging connected components in a similarity graph (e.g., approximate nearest-neighbor links between embeddings). Build edges between items whose embedding distance < threshold, then use union-find to merge connected groups efficiently. Compared to repeated BFS/DFS, union-find handles incremental unions online and at scale (millions of items) with near-constant per-operation cost, enabling fast clustering/connected-component labeling during preprocessing.

HardTechnical

64 practiced

Given two rooted trees representing hierarchical taxonomies, design an algorithm to compute a minimum edit sequence (node moves, renames) to transform one taxonomy into the other. Discuss approximate and exact approaches, tree edit distance algorithms, and complexity. Explain how this applies to merging label ontologies across datasets in AI projects.

Sample Answer

Clarifying requirements and cost model- Decide allowed operations and costs: rename (label change), insert, delete, and move (re-parent). Moves are especially important for taxonomies but change algorithmic complexity. Also decide whether trees are ordered or unordered, and whether node identity (stable IDs) exists.

Exact algorithms- Ordered trees (no explicit move): use tree edit distance (TED) algorithms — Zhang-Shasha (classic) or APTED (more recent, faster in practice). They compute minimum-cost sequence of insert/delete/rename. Zhang-Shasha runs roughly O(n1 * n2 * (deg1+deg2)) in practice; worst-case cubic behavior; APTED is highly optimized and robust for real taxonomies.- With explicit moves: allowing cut-and-paste (move) makes the problem much harder. Minimum-edit with moves can be reduced to constrained matching problems; in general the optimal sequence with moves is NP-hard (moves introduce global dependencies). Exact solutions require exponential-time search (A* over mapping space) and are feasible only for small trees.

Approximate and practical approaches- Reduce moves to cheaper delete+insert when acceptable; TED then gives a baseline.- Greedy move-first heuristics: identify high-similarity subtrees (by label similarity + structure), perform move if it reduces cost, repeat.- Mapping + matching: compute bipartite matching between nodes (cost = rename + moving cost inferred from best reparenting), solve minimum-weight matching to get correspondences, then derive edits. Use Hungarian algorithm for matching (polynomial).- Local search / hill-climbing: start from TED mapping, propose moves/renames, accept if cost decreases.- Embedding-based clustering: represent label+context by embeddings (BERT, graph embeddings), align semantically similar nodes, then run structural reconciliation heuristics.

Algorithm sketch (practical pipeline)1. Preprocess: normalize labels, compute node embeddings using label text + ancestor path.2. Candidate mapping: for each node in A, find top-k similar nodes in B (cosine on embeddings).3. Initial alignment: solve min-cost bipartite matching over candidate pairs (Hungarian) with costs combining label rename and structural distance.4. Generate edits: for matched nodes, issue renames if labels differ; for unmatched nodes, choose between delete/insert or move candidate if reparenting to matched parent reduces overall cost.5. Improve with local search: attempt subtree moves that reduce total cost; keep moves with positive improvement.6. Human-in-the-loop: present uncertain edits with confidence scores.

Complexity and trade-offs- Exact TED (no moves): polynomial (practical cubic-ish). With moves: NP-hard → use approximations.- Matching step: O(n^3) worst for Hungarian; embedding/pre-filtering reduces candidates.- Local search depends on number of proposals; empirically fast on real taxonomies.

Application to merging label ontologies in AI projects- Semantic alignment: use textual embeddings (domain-tuned BERT) and instance co-occurrence to match concepts across datasets.- Preserve provenance: keep original labels and mapping metadata to allow rollback and auditing.- Iterative integration: align high-confidence nodes automatically, flag ambiguous mappings for human review; propagate merges to dataset labels and retrain models if needed.- Impact on models: consistent, merged taxonomies improve supervision signal and reduce label noise; but moving/merging classes can require dataset relabeling, model fine-tuning, and careful versioning.

Evaluation metrics- Edit cost achieved vs baseline (delete+insert)- Precision/recall of node mappings using a gold alignment- Downstream model metrics (accuracy, F1) after merging- Human annotation overhead (number of queries)

TakeawayUse exact TED (Zhang-Shasha/APTED) when moves are not required; when moves matter, prefer matching+heuristic or embedding-guided local search with human validation to balance quality and scale.

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.