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

112 practiced

Implement iterative inorder traversal of a binary tree in Python without recursion. Signature: def inorder_iterative(root) -> List[int]. Explain the stack invariant you maintain and how this approach helps avoid recursion depth limits in production backend code.

MediumTechnical

62 practiced

Implement Dijkstra's algorithm in Java to compute shortest path distances from a source in a graph with non-negative weights. Signature: Map<Integer, Long> dijkstra(Map<Integer, List<Pair<Integer, Long>>> adj, int source). Use a priority queue and explain time complexity in terms of V and E for both binary-heap and Fibonacci-heap implementations. Also discuss typical backend constraints that might affect your choice of heap.

HardTechnical

84 practiced

Implement Heavy-Light Decomposition (HLD) on a tree to support path queries (e.g., sum or max on a path) and point updates. Provide APIs: build(adj), update(node, value), query(u, v) returning aggregated value on path u-v. Explain how HLD maps tree paths to segments and the complexity of operations. Discuss memory and implementation pitfalls in production code.

HardTechnical

83 practiced

Implement LCA using Euler Tour + Range Minimum Query (RMQ) to achieve O(1) query time after O(N log N) preprocessing. Provide the main steps: build Euler tour, depths array, build sparse table for RMQ, and answer LCA queries. Discuss memory and preprocessing trade-offs compared to binary lifting and when O(1) queries are necessary in backend services.

EasyTechnical

85 practiced

Design encode and decode functions in Python to serialize and deserialize a binary tree into a compact string for storage and transfer. Provide signatures: def serialize(root) -> str and def deserialize(data: str) -> TreeNode. Use a level-order (BFS) representation using a delimiter and explicit null markers, and ensure that serialize followed by deserialize reconstructs the original tree structure.

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.