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

0 practiced

Implement lowest_common_ancestor(root, p, q) for a binary tree (not necessarily a BST) in Python using the recursive approach that returns the node that is the lowest common ancestor of p and q. Explain why this approach works and how it differs from LCA in a BST.

EasyTechnical

0 practiced

Explain when to use adjacency matrix versus adjacency list representations for graphs. For each representation, describe memory usage and time complexity for operations: checking edge existence, iterating neighbors, and adding/removing edges. Give ML-related examples where a dense matrix is preferable (e.g., spectral methods) and where adjacency list is preferable (e.g., sparse GNNs).

MediumTechnical

0 practiced

Implement kruskal_mst(n, edges) in Python to compute the total weight of a Minimum Spanning Tree for an undirected weighted graph with n nodes and edges list (u, v, w). Implement a disjoint set union-find with path compression and union by rank/size. Explain correctness and the algorithm's time complexity.

EasyTechnical

0 practiced

Implement two functions in Python: build_adjacency_list(edges, n) and build_adjacency_matrix(edges, n). edges is a list of tuples (u, v) for an undirected graph with nodes labeled 0..n-1. Return the adjacency list and adjacency matrix respectively. After implementing, discuss time and space complexities and describe scenarios (sparse vs dense graphs) where you would prefer one representation over the other.

EasyTechnical

0 practiced

As an ML engineer, implement predict(instance) in Python for a trained decision tree where each node has attributes: feature_index, threshold, left, right, and leaf prediction. Your function should traverse the tree to a leaf and return the predicted label or score. Explain per-example complexity and optimizations for batch inference in production.

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.