11.1 What is a Tree?
A tree is a connected graph with no cycles. For a graph T with n vertices, the following are all equivalent characterizations — any one can serve as the definition:
| # | Characterization |
|---|---|
| 1 | T is connected and acyclic |
| 2 | T is connected and has exactly n − 1 edges |
| 3 | T is acyclic and has exactly n − 1 edges |
| 4 | Every pair of vertices is joined by a unique path |
| 5 | T is minimally connected: removing any edge disconnects it |
| 6 | T is maximally acyclic: adding any edge creates exactly one cycle |
A forest is any acyclic graph; a forest with n vertices and k components has n − k edges. Instant consequences: a tree with 10,000 vertices has 9,999 edges; every tree with n ≥ 2 vertices has at least 2 leaves (vertices of degree 1).
11.2 Rooted Trees and Binary Trees
Designating a root orients every edge away from it, giving parent/child/ancestor/descendant vocabulary; height = length of the longest root-to-leaf path. An m-ary tree gives each internal vertex at most m children; full means exactly m.
Key counting facts for a full binary tree: with i internal vertices there are i + 1 leaves and n = 2i + 1 vertices total. Example: 100 internal vertices → 101 leaves, 201 vertices. A binary tree of height h has at most 2^h leaves, so a binary tree with l leaves has height h ≥ ⌈log2 l⌉ — this is precisely why comparison-based binary search and balanced BSTs cost Θ(log n), and why a decision tree sorting n items (n! leaves) needs height ≥ log2(n!) = Ω(n log n).
11.3 Worked Example 1 — Traversals of an Expression Tree
Traversal orders for binary trees: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root).
Build the expression tree of **(a + b) (c − d)*: root *, left subtree + over a, b; right subtree − over c, d.
- Preorder: * + a b − c d — exactly prefix (Polish) notation.
- Inorder: a + b * c − d — infix, but ambiguous without parentheses.
- Postorder: a b + c d − — postfix (Reverse Polish), evaluated by a stack with no parentheses: push a, b → apply + → push c, d → apply − → apply . With a = 6, b = 2, c = 9, d = 4: stack computes 8, then 5, then 40. Compilers and calculators evaluate expressions this way.
Second traversal check: insert 50, 30, 70, 20, 40, 60, 80 into a binary search tree. Inorder yields 20 30 40 50 60 70 80 — sorted order (the defining property of BSTs); preorder yields 50 30 20 40 70 60 80, which is the order you would store to rebuild the same BST.
11.4 Spanning Trees
A spanning tree of a connected graph G is a subgraph that is a tree containing every vertex of G. Every connected graph has one (grow via BFS or DFS). Cayley's formula: K_n has n^(n−2) spanning trees — K4 has 4^2 = 16. Removing any spanning tree's edges from a connected graph with e edges cuts e − (n − 1) independent cycles.
11.5 Worked Example 2 — Minimum Spanning Tree by Kruskal
Weighted graph on {A, B, C, D, E}: AB = 2, AC = 3, BC = 1, BD = 4, CD = 5, CE = 6, DE = 7. Kruskal: sort edges ascending; accept an edge unless it closes a cycle; stop at n − 1 = 4 edges.
| Step | Edge | Weight | Decision |
|---|---|---|---|
| 1 | B–C | 1 | Accept |
| 2 | A–B | 2 | Accept |
| 3 | A–C | 3 | Reject — A, C already connected (cycle A-B-C) |
| 4 | B–D | 4 | Accept |
| 5 | C–D | 5 | Reject — cycle B-C-D... (D reachable) |
| 6 | C–E | 6 | Accept — 4 edges reached, stop |
MST = {BC, AB, BD, CE}, total weight 1 + 2 + 4 + 6 = 13. Prim's algorithm (grow one tree from a start vertex, always adding the cheapest edge leaving it) returns the same weight; when all edge weights are distinct the MST is unique. Cycle detection in Kruskal is implemented with union–find on the equivalence classes of "connected so far" — Unit 1's relations at work.
11.6 Common Mistakes & CS Applications
- Inorder traversal is meaningful only for binary trees; preorder/postorder generalize to any rooted tree.
- A spanning tree spans vertices, not edges; a graph usually has many spanning trees but a tree has exactly one (itself).
- Confusing height ⌈log2 l⌉ lower bound (best case) with actual height — an unbalanced BST can degenerate to height n − 1.
- Applications: file systems, XML/JSON documents, and parse trees are rooted trees; MSTs design least-cost networks (LAN cabling, clustering); Huffman coding builds an optimal prefix-code tree; spanning-tree protocol (STP) keeps Ethernet loop-free.
🎯 Exam Focus
- Prove that a tree with n vertices has exactly n − 1 edges (induction on n).
- A full binary tree has 63 vertices. How many internal vertices, leaves, and what is the minimum possible height?
- Draw the expression tree for a * (b + c) − d / e and write its preorder, inorder, and postorder traversals.
- Define spanning tree. How many spanning trees does C5 have? K4? Justify.
- Run Kruskal's algorithm on: AB=4, AC=1, BC=2, BD=5, CD=8, CE=10, DE=2, DF=6, EF=3 — list accepted edges in order and the MST weight.
- Prove that every tree is a bipartite graph.