Basics of graphs
A graph is a set of vertices joined by edges. Pick a chapter: the parts of a graph, degrees, paths and cycles, distances, the types of graphs, a graph that becomes a binary search tree one restriction at a time, and the shapes binary trees come in.
From a graph to a binary search tree
Each name is the one before it with one more rule. The "Graph → BST" chapter walks the same seven vertices down this list.
- Pseudo graph: any vertices and edges, self-loops and parallel edges allowed.
- Multigraph: no self-loops.
- Simple graph: at most one edge between two vertices.
- Directed graph: every edge has a direction.
- DAG: no directed cycle.
- Tree: connected, with n − 1 edges (so no cycle even ignoring directions).
- Rooted tree: one root, every edge pointing away from it (every other vertex has one parent).
- Binary tree: at most two children, each a left or a right child.
- Binary search tree: left subtree's keys < vertex's key < right subtree's keys.
- Balanced BST: every vertex's two subtrees within one level of each other, so height ≈ log₂ n.