Trees & Graphs

A traversal is a fixed order for visiting every node of a tree once: preorder, inorder and postorder go deep first, level order goes row by row.

A binary search tree keeps every left subtree smaller and every right subtree larger than its node, so search, insert and delete follow one path and cost O(height).

Most tree problems are solved by asking each subtree a question, trusting the recursive answer, and combining the left and right answers at the node.

A graph is nodes plus edges, and you store it as an adjacency list, an adjacency matrix, an edge list, or implicitly as a grid, choosing by size, density and the queries you need.

BFS explores a graph in rings of increasing distance using a queue, so the first time it reaches a node is along a shortest path when all edges cost the same.

DFS follows one path as deep as it can before backing up, which makes it the natural tool for exploring regions, finding connected components and detecting cycles.

A topological sort lists the nodes of a directed acyclic graph so that every edge points forward, giving a valid order for tasks with dependencies, and it exists only if there is no cycle.

Dijkstra's algorithm finds the cheapest path from one source to every node when edge weights are non-negative, by always settling the closest unsettled node next using a min-heap.

Union-find keeps track of which items belong to the same group and merges groups in nearly constant time, using a parent pointer per item, path compression and union by size.