Trees

Why trees matter

In graphs, you often face a tension:

• •You want connectivity (everything can reach everything).
• •But extra edges can create cycles, which can cause redundancy, ambiguity in “the path,” and algorithmic overhead.

A tree hits a sweet spot: it’s connected, but it has no cycles. That means it has exactly the minimum number of edges needed to stay connected.

Definition (undirected)

A tree is an undirected graph $G = (V, E)$ such that:

1) Connected: for any vertices $u, v \in V$, there exists a path between them.

2) Acyclic: there is no cycle (no closed loop of distinct vertices/edges).

You can think of a tree as a structure where edges form “branches” that never loop back.

A quick intuition

Imagine building a network by adding edges one at a time:

• •If you start with $n$ isolated vertices, you have $n$ connected components.
• •Each time you add an edge between two different components, you reduce the component count by 1.
• •If you ever add an edge within the same component, you create a cycle.

A tree is exactly the state where:

• •you’ve reduced components down to 1 (connected),
• •and you never created a cycle.

Key equivalences (the “triangle” to remember)

For a finite undirected graph $G = (V, E)$, the following are equivalent:

1) $G$ is a tree (connected + acyclic)

2) There is a unique simple path between any two vertices

3) $G$ is connected and has exactly $$|E| = |V| - 1$$

These equivalences are not trivia—they’re the fastest way to recognize and reason about trees.

Visualization idea for an interactive canvas (recommended)

Use toggles/buttons:

• •Add edge (choose endpoints)
• •Remove edge

And live indicators:

• •|V|, |E|
• •Component count
• •Cycle detector (highlight cycle edges in red)
• •Unique path check (click two nodes → highlight the path; if multiple paths exist, show both)

This setup reinforces the key equivalences:

• •Adding an edge in a connected tree forces a cycle.
• •Removing any edge in a tree disconnects it.
• •As long as you have connected + $|E|=|V|-1$, you must have no cycles.

This section is the backbone. Trees are simple because three different “views” all describe the same object.

A. Why “no cycles” gives unique paths

Assume $G$ is connected and acyclic.

Take any two vertices $u$ and $v$.

• •Because the graph is connected, at least one path exists.
• •Suppose there were two different simple paths from $u$ to $v$.

Then those two paths must diverge at some point and rejoin later, forming a loop—i.e., a cycle. That contradicts acyclic.

So in a connected acyclic graph, the path between any two vertices is unique.

Key intuition:

• •Multiple routes between the same two nodes implies there’s a way to go out along one route and come back along another → a cycle.

B. Why unique paths forbid cycles

Now assume between any two vertices there is a unique simple path.

• •If a cycle existed, pick two vertices on that cycle.
• •Going around the cycle clockwise vs counterclockwise gives two different simple paths between the same vertices.

Contradiction. So there can be no cycles.

C. Where does |E| = |V| − 1 come from?

This is the “edge counting” signature of trees.

Claim

If $G$ is a tree with $n = |V|$ vertices, then it has exactly $|E| = n - 1$ edges.

Proof idea (slow and intuitive)

Start from a single vertex:

• •With $1$ vertex, a tree has $0$ edges.

Now imagine building any tree by adding one new vertex at a time.

• •To keep the graph connected, each new vertex must be connected by at least one edge.
• •To avoid creating a cycle, that new vertex cannot connect with two edges into the existing connected structure.

So each time you add a vertex, you add exactly one edge.

After adding up to $n$ vertices:

• •edges = $(n - 1)$

A more “component count” perspective

Let’s start with $n$ isolated vertices. Components = $n$.

Each edge that connects two different components reduces components by 1.

To reach 1 component, you must reduce by $(n - 1)$, requiring at least $(n - 1)$ edges.

A tree is cycle-free, meaning you never waste an edge inside a component. So it uses exactly $(n - 1)$ edges.

D. Two “surgery” facts (great for visualization)

These are extremely useful and very testable in an interactive canvas.

Fact 1: Add an edge to a tree ⇒ exactly one cycle appears

Let $T$ be a tree. Pick any two vertices $u, v$.

• •In a tree there is a unique path from $u$ to $v$.
• •If you add the edge $(u, v)$, you create a loop: that path plus the new edge.

So one extra edge over $|V|-1$ forces a cycle.

Fact 2: Remove any edge from a tree ⇒ it disconnects

Take any edge $e$ in a tree.

• •Because paths are unique, that edge lies on the unique path between its endpoints.
• •Removing it destroys that only route.

So every edge is a bridge (a cut edge) in a tree.

E. A compact equivalence summary

For a finite undirected graph, any two of the following imply the third:

• •connected
• •acyclic
• •$|E| = |V| - 1$

This is a powerful “tree detector.”

Mini-table: how to use the equivalences

(That last row surprises people: if you have no cycles and still have $n-1$ edges, you can’t afford to be disconnected.)

So far, trees were undirected: edges have no orientation. Many applications (hierarchies, parsing, search) need direction—so we pick a root.

A. Rooted tree: turning an undirected tree into a hierarchy

A rooted tree is a tree with one distinguished vertex called the root (often written $r$).

Once you choose a root, every other vertex $x$ has:

• •a unique path from $r$ to $x$ (because the underlying graph is a tree)
• •therefore a unique previous vertex on that path

That previous vertex is the parent.

Parent function

For a rooted tree with root $r$:

• •$\text{parent}(r)$ is undefined (or sometimes set to null)
• •for any $x \neq r$, $\text{parent}(x)$ is the neighbor of $x$ on the unique path from $r$ to $x$

You can define it formally:

• •Let the unique path from $r$ to $x$ be $(r = v_0, v_1, \dots, v_k = x)$.
• •Then $$\text{parent}(x) = v_{k-1}.$$

B. Children, ancestors, descendants

Once parent is defined:

• •$y$ is a child of $x$ if $\text{parent}(y) = x$.
• •$x$ is an ancestor of $y$ if $x$ lies on the path from $r$ to $y$.
• •$y$ is a descendant of $x$ if $x$ is an ancestor of $y$.

These relationships are not extra edges—they are interpretations of the same undirected structure after choosing a root.

C. Leaves

A leaf (in a rooted tree) is a node with no children.

Important subtlety:

• •In an undirected tree, a leaf is usually defined as a vertex of degree 1 (when $|V|>1$).
• •In a rooted tree, “leaf” depends on orientation: it means no children.

These align nicely when the root is not isolated:

• •A vertex of degree 1 in the undirected sense will be a leaf for any root not equal to that vertex.
• •The root can be a leaf only in the degenerate 1-vertex tree.

D. Depth and height (useful derived notions)

With a root, you can measure “how far down” nodes are.

• •Depth of a node $x$: number of edges on the path from $r$ to $x$.
• •Height of the rooted tree: maximum depth of any node.

These quantities matter in algorithmic runtime (e.g., searching a deep tree can be costly).

E. Visualization hooks for rooted trees

On an interactive canvas:

• •Add a “Choose root” tool: click a vertex to mark it as root.
• •Automatically orient edges away from root (draw arrows or place parent pointers).
• •When you click a node $x$, display:
• •$\text{parent}(x)$
• •list of children
• •depth
• •Highlight leaves in a distinct style.

This makes the idea of “parent(x) is defined by the unique path to root” concrete.

Trees show up whenever you want structure without ambiguity.

A. Modeling hierarchies

• •File systems: folders contain subfolders/files (a rooted tree if you ignore links).
• •Organization charts: manager (parent) → reports (children).
• •Taxonomies: category/subcategory relationships.

Root choice is natural here (CEO, root directory, etc.).

B. Algorithm design on trees

Trees are friendly because:

• •Unique paths simplify reasoning.
• •Many problems become solvable with DFS/BFS in linear time $O(|V|)$.

Typical tasks:

• •compute depths, parents
• •find lowest common ancestor (later topic)
• •dynamic programming on trees (later topic)

C. Relationship to spanning trees (preview)

Given a connected graph with cycles, a spanning tree is a subgraph that:

• •includes all vertices
• •is a tree (so it has $|V|-1$ edges)

So a spanning tree is what you get when you “remove enough edges to break all cycles but keep connectivity.”

This connects directly to Minimum Spanning Trees (MST): among all spanning trees, choose minimum total weight.

D. Relationship to Disjoint Sets (Union-Find) (preview)

Union-Find helps track connected components as you add edges.

That aligns perfectly with the “tree building” view:

• •Each edge connecting two components reduces component count.
• •An edge within a component creates a cycle.

That’s exactly what Kruskal’s MST algorithm uses Union-Find to detect.

E. Trees as data structures (preview)

When you restrict the shape or labeling of a rooted tree, you get powerful data structures:

• •Binary Trees: each node has ≤ 2 children.
• •Tries: edges labeled by characters; paths represent strings.

These will reuse the parent/child/leaf vocabulary heavily.