Core Concepts

• 1BFS — why it finds shortest paths in unweighted graphs: BFS explores nodes in order of their distance from the source. It uses a queue (FIFO) to ensure that all nodes at distance d are processed before any node at distance d+1. This layer-by-layer expansion is precisely why BFS discovers the shortest path first — the first time BFS reaches a node, it has taken the fewest possible edges to get there. In a weighted graph where all edges have equal weight, BFS gives shortest paths. In trees, BFS gives level-order traversal. Key implementation: use a deque (collections.deque) and a 'visited' set (or modify the grid/matrix in-place) to avoid revisiting nodes. O(V+E) time and space.
• 2DFS — structure and the call stack: DFS explores as deep as possible before backtracking. Recursive DFS uses the implicit call stack; iterative DFS uses an explicit stack. In trees, DFS gives preorder (root, left, right), inorder (left, root, right), and postorder (left, right, root) traversals. Inorder of a BST gives sorted order — this is the key BST property. Preorder is useful for serialization (you can reconstruct the tree). Postorder is useful when you need children's results before the parent's (e.g., computing subtree heights, aggregating values up the tree). DFS is O(V+E) time and O(V) space for the call stack (O(h) for trees where h is height).
• 3BST operations and the BST invariant: every node in a BST satisfies: all nodes in its left subtree have smaller values, all nodes in its right subtree have larger values. This invariant enables O(h) search, insertion, and deletion (h = tree height; O(log n) for balanced trees, O(n) worst case for degenerate trees). Validation (LC 98) requires passing min/max bounds down the recursion — checking left.val < node.val is NOT sufficient because the constraint must hold for the entire subtree. Deletion is the trickiest operation: if the node has two children, replace it with the inorder successor (smallest node in right subtree) and delete the successor from the right subtree.
• 4Lowest Common Ancestor (LCA): for a binary tree (not necessarily BST), the LCA of nodes p and q is the deepest node that has both p and q as descendants. The recursive approach: if root is None, p, or q — return root. Recurse on left and right subtrees. If both return non-None, root is the LCA. If only one returns non-None, that subtree contains both p and q (they are nested). This bottom-up DFS is O(n). For BSTs specifically, use the BST property: if both p and q are less than root, go left; if both greater, go right; otherwise root is the LCA — O(h) time.
• 5Serialize and deserialize binary tree: the key insight is that preorder traversal with null markers uniquely identifies the tree. Serialization: preorder DFS, output node values with 'N' for null, comma-separated. Deserialization: process values left-to-right with a recursive function that consumes the next value for the current node. If the value is 'N', return None (null node). The recursive call structure mirrors the preorder construction. BFS-based serialization is also valid and matches LeetCode's display format. O(n) time and space for both operations.
• 6Topological sort — Kahn's algorithm (BFS) vs DFS: topological sort orders nodes such that for every directed edge u→v, u appears before v. Only possible in DAGs (directed acyclic graphs). Kahn's algorithm: compute in-degrees of all nodes. Add all nodes with in-degree 0 to a queue. Repeatedly dequeue a node, add to result, and decrement neighbors' in-degrees — if any reach 0, enqueue them. If result size < total nodes, a cycle exists. DFS approach: DFS on all unvisited nodes; after fully processing a node (all descendants visited), push it to a stack. Result is the reverse of the stack's pop order. Cycle detection: if you encounter a node in the 'currently being visited' set (gray node), a cycle exists. O(V+E) for both.
• 7Dijkstra's algorithm — why it works: Dijkstra finds shortest paths from a source to all nodes in a weighted graph with non-negative edge weights. It uses a min-heap (priority queue) keyed by tentative distance. The key invariant: when a node is popped from the heap, its distance is finalized (no shorter path can exist). This works because all edge weights are non-negative — relaxing an edge can only make distances smaller, but we've already confirmed the popped node's distance is minimal. For negative weights, Bellman-Ford is needed. O((V+E) log V) with a binary heap. In Python: use heapq with (distance, node) tuples. Always check if the popped distance matches the current best distance — skip if stale.
• 8Union-Find (Disjoint Set Union): efficiently manages a partition of elements into disjoint sets with two operations: find(x) returns the representative (root) of x's set; union(x, y) merges the sets containing x and y. Two key optimizations: (1) Path compression: during find, make every node on the path point directly to the root. (2) Union by rank: always attach the shorter tree under the taller tree's root. Together, these give amortized O(α(n)) per operation where α is the inverse Ackermann function — effectively O(1). Use cases: connected components, cycle detection in undirected graphs (if union returns false — nodes already connected — there's a cycle), Kruskal's MST algorithm.
• 9BFS vs DFS vs Dijkstra — when to use which: BFS for shortest path in UNWEIGHTED graphs (or graphs where all edge weights are equal) — O(V+E). Dijkstra for shortest path in WEIGHTED graphs with non-negative weights — O((V+E) log V). DFS for: tree structure problems (height, diameter, path sums), cycle detection, connected components, topological ordering, backtracking. Union-Find for: dynamic connectivity queries, cycle detection in undirected graphs, minimum spanning tree (Kruskal's). A common mistake: using DFS to find shortest paths — DFS finds A path, not necessarily the shortest. Another mistake: using Dijkstra on graphs with negative weights — use Bellman-Ford or SPFA instead.

Key Patterns & Templates