Top 45 Trees & Graphs Interview Questions 2025

DFS traversals: Inorder (left, root, right) - BST gives sorted order, Preorder (root, left, right) - copy tree, serialize, Postorder (left, right, root) - delete tree, evaluate expressions. BFS: Level order using queue - level-by-level processing. Iterative versions use explicit stack. Time: O(n) for all.

Balanced: height difference of left and right subtrees <= 1 for every node. Naive: O(n²) checking height at each node. Optimal O(n): return -1 for unbalanced, otherwise return height. At each node: get left height, right height, if either -1 or diff > 1 return -1, else return max(left, right) + 1.

LCA: deepest node that is ancestor of both given nodes. BST: compare values, go left/right based on both nodes. Binary tree: recursive - if root is null or matches either node, return root. Recurse left and right. If both return non-null, root is LCA. If one null, return other. O(n) time, O(h) space.

BFS (queue): explores level by level, finds shortest path in unweighted graph, uses more memory (stores entire level). DFS (stack/recursion): explores deep first, uses less memory, good for detecting cycles, topological sort. BFS for: shortest path, level order. DFS for: cycle detection, connected components, topological sort.

DFS with coloring: WHITE (unvisited), GRAY (in current path), BLACK (fully processed). Cycle exists if we reach GRAY node. Alternative: track recursion stack alongside visited set. For undirected: track parent - cycle if neighbor is visited and not parent. Topological sort: cycle if not all nodes processed.