Trees as Special Graphs: Structure & Traversal

Graph Theory

Chapter 9 · Trees as Special Graphs: Structure & Traversal

Trees have already shown up twice without ever being the main subject — Chapter 4's own finding-box noted that a tree with V vertices has exactly V−1 edges and no cycles, and Chapter 8 built an entire algorithm family around finding one. This chapter finally gives trees their own spotlight: what they're made of, and how the traversal ideas from Chapters 3 and 5 turn out to already be exactly what a tree needs.

A Tree Is Just a Connected, Acyclic Graph

A (free) tree is an undirected graph that is both connected (every vertex reachable from every other) and acyclic (no cycles at all — not even the parent-tracking exception from Chapter 4's undirected cycle check, since a tree has no cycles whatsoever). Any two of the following three properties automatically guarantee the third, for a graph with V vertices:

Given	Then automatically
Connected + acyclic	Exactly `V−1` edges
Connected + exactly `V−1` edges	Acyclic
Acyclic + exactly `V−1` edges	Connected

Verified on this chapter's own worked example

The tree below has V=7 vertices and E=6 edges — exactly V−1, matching every one of the equivalences above.

Rooted Trees: Adding a Direction

A free tree has no designated starting point. Picking one vertex as the root turns it into a rooted tree, which unlocks a whole vocabulary: the root's neighbors become its children, and it becomes their parent; a vertex with no children is a leaf; a vertex's depth is its distance from the root; a tree's height is the greatest depth any vertex reaches; the vertex and everything reachable below it form a subtree.

Worked example, rooted at A: A→{B,C,D}, B→{E,F}, D→{G} (C, E, F, G are leaves).

Verified directly

Depths: A=0, B=1, C=1, D=1, E=2, F=2, G=2. Height of the tree: 2 (the deepest leaves, E/F/G, are 2 steps from the root).

Scope note: binary trees

A binary tree restricts every node to at most 2 children (conventionally "left" and "right") — the structure behind binary search trees and heaps. Balancing, searching, and insertion into binary trees are their own substantial topic and stay out of this course's scope; what matters here is that they're still just rooted trees, and everything below still applies to them directly.

Traversal Orders: Not New Algorithms, Just Named Moments

A tree has exactly one simple path between any two vertices, so DFS never needs Chapter 4's back-edge check at all — there's nothing to loop back on. On a rooted tree, the only real choice left is when to process ("visit") a node relative to visiting its children:

Order	When the node is visited	Already met as
Pre-order	Before any of its children	The order Chapter 3's DFS naturally visits vertices in
Post-order	After all of its children	Exactly Chapter 5's own DFS finish order — the stack topological sort was built on
Level-order	By depth, shallowest first	Exactly Chapter 3's own BFS

Traced and verified directly, on the same rooted tree above

Pre-order: A, B, E, F, C, D, G — each node written down the instant it's first reached.
Post-order: E, F, B, C, G, D, A — each node written down only once every child beneath it is done, the root inevitably last.
Level-order (BFS): A, B, C, D, E, F, G — depth 0, then all of depth 1, then all of depth 2.

No new machinery was needed for any of these — pre-order is DFS with no back-edges to worry about, post-order is Chapter 5's finish-order stack read directly instead of reversed (a tree, being acyclic, never needs the reversal that made a topological order valid), and level-order is Chapter 3's BFS applied to a graph that happens to be a tree.

Real Relevance: File Systems, Org Charts & the DOM

A file system is a rooted tree — folders as internal nodes, files as leaves; walking it top-down before descending into each subfolder (exactly how a tool like os.walk or a recursive directory listing behaves) is pre-order traversal. An org chart is a rooted tree of reporting relationships. A web page's DOM is a rooted tree of elements, and a JSON or XML document parses into one too — nested objects and arrays as subtrees. Anywhere a "contains" or "reports to" relationship never loops back on itself, the natural model is a tree, and one of these three traversal orders is almost always the right way to walk it.

Tree Traversal in Code

def preorder(tree, node, out=None):
    if out is None: out = []
    out.append(node)                       # visit BEFORE children
    for child in tree[node]:
        preorder(tree, child, out)
    return out

def postorder(tree, node, out=None):
    if out is None: out = []
    for child in tree[node]:
        postorder(tree, child, out)
    out.append(node)                       # visit AFTER children
    return out

from collections import deque
def level_order(tree, root):
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node)
        for child in tree[node]:
            q.append(child)
    return out

org_chart = {'A': ['B','C','D'], 'B': ['E','F'], 'C': [], 'D': ['G'], 'E': [], 'F': [], 'G': []}
print(preorder(org_chart, 'A'))      # ['A','B','E','F','C','D','G']
print(postorder(org_chart, 'A'))     # ['E','F','B','C','G','D','A']
print(level_order(org_chart, 'A'))   # ['A','B','C','D','E','F','G']

Hands-On Exercises

Exercise 1

A file system has: root→{docs, src}, docs→{readme.txt}, src→{main.py, utils.py}. Write out the pre-order and post-order traversals starting from root, and state which one matches how a real directory listing tool typically prints folders before descending into them.

📄 View solution

Exercise 2

For the same file system tree from Exercise 1, compute the depth of every node and state the tree's height.

📄 View solution

Exercise 3

Explain, using this chapter's own definitions, why post-order traversal always visits the root last, and why pre-order traversal always visits the root first — for any rooted tree, not just this chapter's specific examples.

📄 View solution

Chapter 9 Quick Reference

Tree: a connected, acyclic graph — any two of {connected, acyclic, V−1 edges} imply the third
Rooted tree terms: root, parent, child, leaf, depth (distance from root), height (max depth), subtree
Pre-order: visit before children — Chapter 3's DFS order
Post-order: visit after children — exactly Chapter 5's DFS finish-order stack
Level-order: visit by depth — exactly Chapter 3's BFS
Real use: file systems (pre-order), org charts, the DOM, JSON/XML structure
Next chapter: Capstone — modeling and solving a real graph problem