Trees and Graphs
Graphs
A graph is a set of nodes (vertices) connected by edges. Graphs model networks — roads, social connections, the internet.
- Directed graph (digraph): edges have a direction (one-way).
- Undirected graph: edges work both ways.
- Weighted graph: each edge has a value (cost/distance/time).
Representing graphs
| Representation | How | Best when |
|---|---|---|
| Adjacency matrix | A grid; entry (i,j) marks/weights an edge between i and j | Graph is dense (many edges); fast lookup |
| Adjacency list | Each node stores a list of its neighbours | Graph is sparse (few edges); saves memory |
A matrix uses O(n²) space regardless of edges; a list uses space proportional to the number of edges.
Trees
A tree is a special connected, undirected graph with no cycles. It has a root node, parent/child relationships, leaf nodes (no children), and a subtree below any node.
Binary tree
Each node has at most two children (left and right). A binary search tree (BST) keeps them ordered: for every node, left subtree < node < right subtree. This gives fast O(log n) search, insert and delete when balanced.
Inserting into a BST: start at the root; go left if smaller, right if larger; place the new node at the empty spot found.
Tree traversals
Ways to visit every node of a binary tree (usually written recursively):
- Pre-order (Node → Left → Right): visit the node first. Used to copy a tree or output prefix notation.
- In-order (Left → Node → Right): visits a BST in ascending order.
- Post-order (Left → Right → Node): visit the node last. Used to delete a tree or produce Reverse Polish (postfix).
Memory aid: the position of "Node" (pre/in/post) tells you when it's visited.
Uses
- BSTs: fast searching/sorting of dynamic data.
- Graphs: shortest-path problems, networks, web page links, dependency resolution.
Worked example
For a BST, which traversal outputs the values in ascending order?
- In-order (Left → Node → Right) — it visits smaller values before larger ones, giving sorted output. ✓
Common mistakes
- Confusing a tree (no cycles, has a root) with a general graph.
- Mixing up the three traversals — remember where Node sits in the name.
- Saying a BST is always O(log n) — that's only when balanced; a skewed BST degrades to O(n).
Exam tips
- Learn the three traversals and one use of each (in-order = sorted output).
- Compare adjacency matrix vs list by density and memory.
- Be ready to trace a BST insertion and a traversal on a diagram.
Key facts to remember
- Graph = nodes + edges (directed/undirected/weighted); store as adjacency matrix (dense) or list (sparse).
- Tree = connected acyclic graph with a root; a BST keeps left < node < right for O(log n) operations when balanced.
- Traversals: pre-order (copy), in-order (sorted BST output), post-order (delete / RPN).