Trees: Traversal, Spanning Trees & MST

A tree is a graph with no loops at all — the simplest possible connected graph, and the one computers use most. This unit is about organising data in a tree, walking through a tree in a fixed order, and finding the cheapest way to connect everything.

Definition

A tree is a connected, acyclic, undirected graph.

Equivalently — and this is the version to memorise — a connected graph with n vertices has exactly n − 1 edges, and if it has n − 1 edges and no cycles then it is a tree.

On this page

Tree terminology
Tree traversal: pre, in, post
Why in-order only works for binary trees
Spanning trees
Kruskal's algorithm
Prim's algorithm
Kruskal vs Prim
Self-check

1. Tree Terminology

7 vertices, 6 edges. Count them — the n − 1 rule holds, which confirms it is a tree.

Term	Meaning
Root	The top vertex. Every tree has exactly one designated root
Parent / child	A vertex one level closer to the root is the parent; one further away is a child
Siblings	Vertices sharing the same parent
Leaf / terminal node	A vertex with no children (degree 1 in an undirected tree, except a single-vertex tree)
Ancestor / descendant	Any vertex on the path up to / down from the root
Level / depth	Distance from the root. A tree rooted at A: A is level 0, its children level 1
Height	The number of edges on the longest root-to-leaf path
Diameter	The longest path between any two vertices (not necessarily through the root)
Degree	Number of children. The root's "degree" is also its number of children
Subtree	A tree formed by a vertex and all its descendants
Ordered tree	Children are in a fixed left-to-right order. BSTs require this
Binary tree	Each vertex has at most 2 children, called left and right
Full binary tree	Every vertex has 0 or exactly 2 children
Balanced	The left and right subtrees of every node differ in height by at most 1. O(log n) search

The facts that define a tree • |E| = |V| − 1 (exactly n − 1 edges)
• Unique path between every pair of vertices (this is why trees are so useful — one route, no ambiguity)
• No cycles
• Adding any extra edge creates a cycle → therefore removing any edge splits it in two

How to check "is this a tree?"

Is it connected? (can you reach every vertex?)
Does it have n − 1 edges? Count them.
Both yes → it is a tree. Either no → it is not.

Connected with more than n − 1 edges means it has a cycle somewhere. That check is fast and reliable, and it is exactly what the question is usually testing.

2. Tree Traversal

Traversal means visiting every node once in a fixed order. The three orders differ in one thing only — when you record the node itself relative to its children.

PRE-ORDER

Node, Left, Right

Record the node BEFORE its children

IN-ORDER

Left, Node, Right

Record the node BETWEEN its children

POST-ORDER

Left, Right, Node

Record the node AFTER its children

PRE = root first, IN = root in the middle, POST = root last. The order never changes — only the position of the node.

Worked example — all three traversals on one tree

Pre-order (Node, Left, Right) — visit root, then left subtree, then right:

50, 30, 20, 40, 35, 45, 70, 60, 80

Post-order (Left, Right, Node) — finish both subtrees first, root last:

20, 35, 45, 40, 30, 60, 80, 70, 50

In-order (Left, Node, Right) — always take the leftmost available node first:

20, 30, 35, 40, 45, 50, 60, 70, 80

Notice what just happened

The in-order traversal came out in sorted order. That is not a coincidence — it is the defining property of a binary search tree. If you are ever given a BST and asked for the in-order traversal, you can skip the whole procedure and just write the values in ascending order. Instant full marks.

Pre: 50, 30, 20, 40, 35, 45, 70, 60, 80
In: 20, 30, 35, 40, 45, 50, 60, 70, 80 (sorted!)
Post: 20, 35, 45, 40, 30, 60, 80, 70, 50

Trick — walk the tree correctly the first time

Students usually get the left/right order wrong, not the pre/in/post part. Two habits:

Always go left first. For in-order, keep moving left until you hit nothing, then record. For pre-order, record the node, then go left.
Cross out each node as you record it. You must not record it twice. In exam conditions this is the single most reliable way to avoid losing marks.

Sanity checks you can do in 2 seconds:

Pre-order starts with the root. In-order has the root in the middle (for a complete tree). Post-order ends with the root.
All three traversals contain exactly the same n values, just reordered.
In-order on a BST is ascending. If yours is not, you have made an error.

Where each traversal is actually used

Traversal	Used for	Why
Pre-order	Copying a tree, or making a prefix expression	Root data is written first, so the structure can be rebuilt from the string
In-order	Sorted output from a BST; finding the k-th smallest value	Yields ascending order
Post-order	Deleting a tree, or a postfix expression (reverse polish)	Children are removed before the parent, so nothing is orphaned

Bonus: post-order of a binary expression tree gives postfix (3 4 +); in-order gives infix (3 + 4); pre-order gives prefix (+ 3 4). Exams love this.

3. Why In-Order Needs a Binary Tree

Important restriction

Pre-order and post-order work on a tree of any shape — they just need "children, from left to right".

In-order only makes sense for a binary tree, because it needs a clear "left child" and "right child" to sit the node between. If a node has three children there is no single "middle" position.

So if a question asks for in-order and the tree is not binary, re-read the question — you have probably been given a BST.

Binary tree size facts • Maximum nodes at depth d (levels 0…d) = 2^d+1 − 1
• Minimum depth (height) for n nodes = ⌊log₂ n⌋
• Minimum height for a full binary tree with n nodes = ⌈log₂(n+1)⌉ − 1

Trick — the complete tree picture

Fill levels left to right, like a heap. A complete binary tree of height h holds 2^h+1 − 1 nodes. Memorise 1, 3, 7, 15, 31, 63 for heights 0, 1, 2, 3, 4, 5. Any "n nodes, what is the minimum height" question is then h = ⌊log₂ n⌋ in about three seconds.

4. Spanning Trees

A spanning tree of a connected graph is a tree that uses every vertex of the graph but only some of the edges — enough to keep everything connected with no cycles.

To get a spanning tree, start with the graph and delete edges until no cycle remains. Stop at n − 1 edges.

Spanning tree facts • Every connected graph has at least one spanning tree
• A spanning tree of a graph with n vertices has exactly n − 1 edges
• A graph can have many spanning trees — that is the motivation for the MST

Trick — cycles and edges

Every cycle you remove costs exactly 1 edge. So if a graph has c independent cycles and m edges, then:

edges you must delete = m − (n − 1) = m − n + 1

Use this to count how many edges to remove. Example: m = 12, n = 8 → remove 12 − 8 + 1 = 5 edges.

Spanning tree vs minimum spanning tree

A spanning tree is any tree covering all vertices — there may be many, and some are expensive.

A minimum spanning tree (MST) is the one with the smallest total edge weight. The previous two algorithms exist to find it.

5. Kruskal's Algorithm

Kruskal builds the MST by repeatedly adding the cheapest edge that does not create a cycle. There is no starting vertex — it works on the whole graph at once, edge by edge.

The algorithm 1. List all edges in ascending order of weight (ties: pick any)
2. Go down the list. Add an edge only if it does not form a cycle
3. Stop when you have added n − 1 edges

The test is always the same: are the two ends already joined by a path of chosen edges? If yes, adding the edge creates a cycle — skip it.

Kruskal worked through

Graph: 6 vertices A–F, edges:

AB=4, AC=1, AD=6, BC=2, BD=5, BE=3, CD=7, CE=8, CF=9, DF=10

Step 1 — sort ascending.

AC(1), BC(2), BE(3), AB(4), BD(5), AD(6), CD(7), CE(8), CF(9), DF(10)

Step 2 — add greedily, skipping cycles.

Edge	Weight	Action	Reason
A–C	1	ADD	Cheapest. No cycle yet.
B–C	2	ADD	Joins B to the component {A,C}.
B–E	3	ADD	Brings in E.
A–B	4	SKIP	A and B are already connected via C → cycle.
B–D	5	ADD	Brings in D. Now 4 edges = 5 − 1.
A–D	6	stop	n − 1 edges reached. Tree complete.

Step 3 — total weight.

1 + 2 + 3 + 5 = 11

MST edges: A–C(1), B–C(2), B–E(3), B–D(5)
Total weight = 11
Shape: C is the hub, connected to A and B; B connects to E and D.
Check: 6 vertices, 4 edges = 6 − 1 ✓. Connect the dots — no loop ✓.

Trick — "union-find" in your head

To check whether an edge creates a cycle, just ask: "is one end already in the same group as the other end?" Sketch the tree as little circles and connect them as you accept edges. If the two ends are already in one circle, skip the edge.

This is the real name of the procedure: the union–find (disjoint set) data structure. Drawing the little circles costs ten seconds and prevents every possible error.

6. Prim's Algorithm

Prim builds the MST the opposite way to Kruskal: it grows outwards from one chosen starting vertex, always adding the cheapest edge that leaves the part of the tree already built.

The algorithm 1. Pick any one starting vertex
2. From the vertices already in the tree, find the cheapest outgoing edge to a new vertex
3. Add that edge and vertex, and repeat
4. Stop when all n vertices are included (n − 1 edges)

The only edge considered at each step is the cheapest one leaving the current tree. Never look at edges wholly inside it.

Prim worked through — the same graph as Kruskal

Edges: AB=4, AC=1, AD=6, BC=2, BD=5, BE=3, CD=7, CE=8, CF=9, DF=10

Step 0 — start at A. Tree = {A}.

Edges leaving A: A–C(1), A–B(4), A–D(6) → pick A–C (1)

Step 1 — tree = {A, C}.

Leaving: A–B(4), A–D(6), C–B(2), C–D(7), C–E(8) → pick B–C (2)

Step 2 — tree = {A, C, B}.

Leaving: A–D(6), B–D(5), B–E(3), C–D(7), C–E(8) → pick B–E (3)

Step 3 — tree = {A, C, B, E}.

Leaving: A–D(6), B–D(5), C–D(7), C–F(9), E–C(8), E–F(10) → pick B–D (5)

Step 4 — 4 edges = 6 − 1. Stop.

Total = 1 + 2 + 3 + 5 = 11

Same answer as Kruskal: A–C(1), B–C(2), B–E(3), B–D(5), total 11.
On a weighted graph both algorithms are correct, so they must agree on the total. (They can pick different edges when weights tie.)

7. Kruskal vs Prim

	Kruskal	Prim
Builds	many small pieces, then merges	one growing tree
Starting point	None — starts anywhere	One chosen starting vertex
Edge choice	Global cheapest available edge	Cheapest edge leaving the current tree
Cycle check	Needed every time	Not needed — impossible by construction
Produces	a forest that becomes a tree	always a single tree
Best when	sparse graphs (many isolated-ish vertices)	dense graphs
Time complexity	O(E log E) — sort the edges	O(E log V) — priority queue
Stops after	n − 1 edges	n − 1 edges

The one-line memory hook

Kruskal = "K"onnect the "K"heapest edges from anywhere. Prim = "P"ick one vertex and g"P"row from it.

Ask yourself this to choose

Does the question give you a start vertex? → Prim
Is the question about joining separate pieces? → Kruskal
Not sure? Either is accepted — write the one you understand better.

If all weights are equal

Both algorithms become meaningless — any spanning tree has the same total. Kruskal then just takes the first n − 1 edges it meets, with no real "cheapest" to speak of.

Marks lost in MST questions

Not sorting the edges first in Kruskal. Sort before you start, and write the sorted list down — the examiner is looking for it.
Adding a cycle-forming edge in Kruskal. Draw the tree as you go.
In Prim, choosing an edge with both ends already inside the tree. Cross out edges that are "used up" once chosen.
Forgetting the total weight is usually required as well as the edge list. Both.
Not stating the final count "4 edges, n − 1 = 4, complete." One line, one mark.

Why any of this matters in computer science

MST — cheapest cabling layout, cheapest road network, network design
Dijkstra (Unit 6) — fastest single route; the cousin of Prim
Traversals — file systems (folders are trees), database indexing, expression evaluation
BSTs — searching n items in only log₂ n steps instead of n
Hashing / tries — trees behind autocomplete and spell-check

Self-check

Open to see the answers

1. Pre-order, in-order and post-order of a BST whose root is 40, left child 20, right child 60; 20 has left child 10 and right child 30; 60 has left child 50 and right child 70.

Pre-order (root, left, right): 40, 20, 10, 30, 60, 50, 70
In-order (left, root, right): 10, 20, 30, 40, 50, 60, 70 — ascending ✓
Post-order (left, right, root): 10, 30, 20, 50, 70, 60, 40

2. How many edges must be deleted to turn a graph with 9 vertices and 14 edges into a tree?

A tree on 9 vertices has 9 − 1 = 8 edges.
Delete 14 − 8 = 6 edges (equivalently m − n + 1 = 14 − 9 + 1 = 6).
This is only valid if the graph is connected — check that first.

3. Run Kruskal on: vertices A,B,C,D,E; edges AB=7, AC=3, AD=9, BC=2, BD=6, BE=5, CD=4, CE=8, DE=1.

Sorted: DE(1), BC(2), AC(3), CD(4), BE(5), BD(6), AB(7), CE(8), AD(9)
DE(1) ADD · BC(2) ADD · AC(3) ADD — now {A,B,C,D,E} with 3 edges
CD(4) SKIP — C and D already connected via A → cycle
BE(5) SKIP — B and E already connected via C, A, D → cycle
MST = {DE, BC, AC}, total = 1 + 2 + 3 = 6. Check: 3 edges = 5 − 1 ✓

4. Is a complete graph K₆ a tree?

No. K₆ has 6 vertices and 6×5/2 = 15 edges, but a tree needs exactly 6 − 1 = 5 edges. It also has many cycles. The only complete graph that is a tree is K₂ (a single edge), and sometimes K₁ is allowed as a trivial one-vertex tree.