Trees & Graphs Basics Questions

Understand binary trees, binary search trees, and basic graph concepts. Know tree traversal methods: in-order, pre-order, post-order, and level-order (BFS). Practice DFS and BFS implementations. Know the difference between directed and undirected graphs. Solve medium-difficulty tree and graph problems.

MediumTechnical

27 practiced

Implement `iterative_postorder(root)` in Python that returns the post-order traversal of a binary tree without recursion using only one explicit stack. Explain the algorithm, how you detect when to process a node, and how to handle skewed trees and edge cases such as single-node trees.

Sample Answer

Approach: Use one explicit stack and a pointer last_visited to know when a node's right subtree has been processed. Push nodes while descending left. At each step, peek the stack:- If peek has a right child not yet visited, move to that right child (push its left spine).- Otherwise, pop and process the node (append to result) and set last_visited to it.

This simulates post-order (left, right, root) without recursion.

python

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

def iterative_postorder(root):
    """
    Return list of node values in post-order using one explicit stack.
    """
    if not root:
        return []
    stack = []
    res = []
    last_visited = None
    node = root

    # Push left spine
    while node:
        stack.append(node)
        node = node.left

    while stack:
        peek = stack[-1]
        # If right child exists and not processed yet, traverse its left spine
        if peek.right and last_visited is not peek.right:
            node = peek.right
            while node:
                stack.append(node)
                node = node.left
        else:
            # Right is None or already processed: safe to process peek
            popped = stack.pop()
            res.append(popped.val)
            last_visited = popped

    return res

Key points:- Detection: last_visited tracks whether we've processed a node's right subtree.- Skewed trees: For left-skewed, algorithm simply descends left and pops nodes; for right-skewed, left spines are single nodes and we traverse right subtrees appropriately.- Edge cases: Empty tree returns []; single-node returns [root.val].

Complexity: Time O(n), Space O(h) where h is tree height (stack).

EasyTechnical

27 practiced

Explain the difference between directed and undirected graphs. Give concrete ML engineering examples for each (for example: web link graphs and citation graphs as directed; user-item bipartite graphs as undirected/bidirectional). Discuss how directionality affects reachability, connectivity, and algorithms like PageRank, topological sort, and shortest path.

Sample Answer

Directed graphs (digraphs) have edges with orientation (u → v). Undirected graphs have symmetric edges (u — v). Directionality changes semantics and which algorithms apply.

Concrete ML engineering examples:- Directed: web link graph (page A links to B), citation network (paper A cites B), user-action sequences (click or follow events). Direction encodes flow, influence, or causality.- Undirected (or effectively bidirectional): user–item bipartite interaction graph when treating interactions as mutual similarity (user connected to item), social friendship networks modeled as undirected, product co-purchase graphs.

How directionality affects properties and algorithms:- Reachability: In directed graphs, reachability is asymmetric — A can reach B without B reaching A (important for influence propagation or causal inference). In undirected graphs reachability is symmetric; connected components suffice.- Connectivity: Directed graphs have strongly connected components (SCCs) and weakly connected components (WCCs). Many ML tasks (e.g., graph embedding) must consider SCCs to avoid mixing unrelated nodes. Undirected graphs use connected components only.- PageRank: Defined on directed graphs — it models random walks following outgoing links; edge direction matters for importance flow. On undirected graphs PageRank reduces to degree-weighted centrality.- Topological sort: Only applies to directed acyclic graphs (DAGs); useful in ML pipelines, task scheduling, and causal structure learning. Not meaningful for undirected graphs.- Shortest path: Algorithms like Dijkstra work for both, but in directed graphs edges are one-way so path existence differs. For ML features (e.g., graph distances for similarity), direction can change distances drastically.

Practical note: when building graph-based ML pipelines, choose whether to preserve direction based on task semantics (causal/influence vs. similarity) and preprocess accordingly (symmetrize, keep direction, or use separate edge types).

EasyTechnical

21 practiced

Implement two functions `dfs_recursive(graph, start)` and `dfs_iterative(graph, start)` in Python to return a list of nodes visited starting from `start`. The graph is provided as an adjacency list dict `{node: [neighbors...]}`. Ensure you correctly handle cycles, disconnected nodes, and large graphs where recursion depth might be an issue in production.

Sample Answer

To traverse an adjacency-list graph with DFS while handling cycles and potential recursion limits, use a visited set to avoid revisiting nodes. Recursive DFS is straightforward but can hit Python recursion limits on deep graphs; iterative DFS (stack) is safer in production.

python

def dfs_recursive(graph, start):
    """
    Recursive DFS returning nodes in visitation order.
    Handles cycles using 'visited' set.
    """
    visited = set()
    order = []

    def dfs(u):
        if u in visited:
            return
        visited.add(u)
        order.append(u)
        for v in graph.get(u, []):
            dfs(v)

    dfs(start)
    return order


def dfs_iterative(graph, start):
    """
    Iterative DFS using an explicit stack to avoid recursion depth issues.
    Uses LIFO stack; we push neighbors in reverse to approximate
    recursive visit order (optional).
    """
    visited = set()
    order = []
    stack = [start]

    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        # Push neighbors; reverse if you want to match recursive ordering
        neighbors = graph.get(u, [])
        for v in reversed(neighbors):
            if v not in visited:
                stack.append(v)

    return order

Key points:- Time: O(V + E); Space: O(V) for visited and recursion/stack.- Edge cases: start not in graph -> functions will treat it as isolated node (returns [start]); empty graph -> [] if start is None or not provided.- For very large/deep graphs prefer dfs_iterative in production; avoid boost of recursion limit unless controlled.

EasyTechnical

24 practiced

Implement two functions in Python: `inorder_recursive(root)` and `inorder_iterative(root)`. Each should return a list of node values in in-order. Assume the node class is: `class Node: def __init__(self, val, left=None, right=None): self.val = val; self.left = left; self.right = right`. For the iterative version avoid recursion and use an explicit stack. State time and space complexity and mention how you'd adapt the recursive version into a lazy generator for streaming.

Sample Answer

To traverse a binary tree in-order (left, node, right) we can implement a simple recursive version and an iterative version using an explicit stack.

python

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

def inorder_recursive(root):
    """Return list of node values in-order using recursion."""
    res = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        res.append(node.val)
        dfs(node.right)
    dfs(root)
    return res

def inorder_iterative(root):
    """Return list of node values in-order using an explicit stack (no recursion)."""
    res, stack = [], []
    cur = root
    while cur or stack:
        # go to leftmost node
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

Key points:- Recursive is straightforward and expressive.- Iterative uses stack to simulate recursion: push left path, pop, visit, go right.

Time complexity: O(n) for both (visit each node once).Space complexity: O(h) auxiliary for stack/recursion depth where h is tree height; worst-case O(n) for skewed tree.

Lazy generator adaptation (streaming) — convert recursive into a generator to yield values one-by-one:

python

def inorder_generator(node):
    if node:
        yield from inorder_generator(node.left)
        yield node.val
        yield from inorder_generator(node.right)

This allows streaming large trees without building the full list in memory; consumption controls memory/time. Iterative generator can be implemented similarly by yielding instead of appending in the loop. Edge cases: empty tree (returns [] or yields nothing), very deep trees (recursive version may hit recursion depth — prefer iterative/generator in production).

HardTechnical

41 practiced

Design an approach to implement parallel BFS-like neighbor sampling on GPUs for large graphs used during GNN training. Explain memory layout (CSR on GPU), batching strategy, warp/coalesced memory accesses, handling variable-degree nodes (high-degree skew), and strategies to avoid memory over-subscription. Provide high-level pseudocode for a sampling kernel and discuss trade-offs.

Sample Answer

Requirements & approach:- Goal: sample K neighbors per seed node in parallel on GPU with BFS-like levels (multi-hop), minimizing memory and maximizing warp-coalesced accesses.- Use CSR (row-pointer + flat neighbor array) resident in GPU global memory; offsets in 32/64-bit depending on graph size.

Memory layout:- row_ptr: int64_t[N+1] (monotonic offsets)- col_idx: int32_t[M] contiguous neighbor IDs- Optionally edge-weight array aligned to col_idx- Keep row_ptr in read-only cache (use __ldg on CUDA) for fast random reads.

Batching strategy:- Process mini-batches of seed nodes sized to fit per-GPU memory and shared-memory budget.- Within a batch, perform level-wise sampling: maintain current frontier (vector of nodes) and next frontier reservoir.- Use two-level batching: global batch of seeds split into warp-block groups to reduce divergence.

Warp/coalesced accesses:- Assign contiguous seeds to threads in a warp so their row_ptr lookups are coalesced.- For scanning neighbors, use segmented-parallel patterns: each warp handles one or a small number of source nodes, and uses warp-wide primitives (shuffle, ballot) to cooperatively fetch neighbor ranges, reading col_idx sequentially for coalescing.- Use gather of neighbor ranges: threads perform vectorized loads (int4/uint4) when scanning long neighbor lists.

Handling variable-degree (skew):- Classify nodes by degree: SMALL (<T1), MEDIUM (T1..T2), LARGE (>T2). - SMALL: one thread per node; iterate neighbors directly. - MEDIUM: one warp per node; cooperative scan + warp-level random selection. - LARGE: dedicate a thread-block; use shared-memory reservoir sampling or pre-sampled indices stored in per-node cache (popular nodes cached).- For high-degree popular nodes, sample without scanning whole list: use random index arithmetic (idx = base + rand()%deg) to read a few entries.

Avoiding memory over-subscription:- Limit total allocated next-frontier size via upper bound: batch_size * K^levels; enforce sampling cap and early duplicate dedup via hash (bloom or per-block bitmap) in shared memory.- Use streaming: if frontier grows too large, split into sub-batches and process sequentially.- Use pooling allocator with pre-allocated buffers to avoid mallocs per kernel.

High-level sampling kernel (pseudocode):

cpp

// pseudo-CUDA kernel
__global__ void sample_kernel(int* row_ptr, int* col_idx, int* seeds, int num_seeds,
                              int K, int* out_neighbors, int* out_counts) {
  int gid = blockIdx.x * blockDim.x + threadIdx.x;
  // warp/degree classification done on host or first warp pass
  for (int s = gid; s < num_seeds; s += gridDim.x*blockDim.x) {
    int v = seeds[s];
    int64_t start = row_ptr[v], end = row_ptr[v+1];
    int deg = end - start;
    if (deg == 0) { out_counts[s]=0; continue; }
    if (deg <= SMALL_T) {
      // thread-local sampling
      int cnt=0;
      for (int i=0; i<deg && cnt<K; ++i) {
        int nbr = col_idx[start + i];
        out_neighbors[s*K + cnt++] = nbr;
      }
      out_counts[s]=cnt;
    } else if (deg <= MED_T) {
      // warp-cooperative sampling (one warp per node)
      // use warp shuffles to generate random offsets and load coalesced
      warp_sample(...);
    } else {
      // block-level sampling/reservoir
      block_sample_large(...);
    }
  }
}

Trade-offs:- Per-node classification reduces divergence but adds pre-processing cost.- Warp-cooperative methods maximize memory bandwidth but increase synchronization and complexity.- Sampling by random index avoids scanning huge adjacency lists but sacrifices exact uniformity unless careful with modulo bias/aliasing.- Deduplication reduces training sample redundancy but costs extra memory/time; bloom filters in shared mem are a good compromise.- Caching neighbors of high-degree nodes trades memory for speed; useful for power-law graphs.

Final tips:- Profile hot paths (memory loads per sample) and tune SMALL/MED/LARGE thresholds to the target GPU.- Use read-only data cache and texture cache for col_idx if pattern benefits.- Combine with host-side prefetch and multiple CUDA streams to overlap data movement and kernel execution.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.