Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 Β· Trees and Spanning Trees

Trees and Forests

Learn what a tree is in graph theory: equivalent definitions, the n-1 edge rule, leaves, forests, rooted trees, center and diameter, with Python code that checks each property.

A tree is a connected graph with no cycles. It is the leanest way to connect a set of vertices: remove any edge and it falls apart, add any edge and a cycle appears. Trees describe file systems, family histories, organization charts, HTML documents, decision processes and the shape of the shortest-path results you computed with BFS and Dijkstra. A graph whose components are all trees is a forest.

graph TD
  r --- a
  r --- b
  a --- c
  a --- d
  b --- e

A tree on 6 vertices and 5 edges. The leaves are c, d, e.

Many ways to say "tree"

For a graph T with n vertices, the following statements are equivalent, and each can serve as a definition:

  1. T is connected and has no cycle.
  2. T is connected and has exactly n - 1 edges.
  3. T has no cycle and exactly n - 1 edges.
  4. Between any two vertices there is exactly one path.
  5. T is connected, and removing any edge disconnects it (every edge is a bridge).
  6. T has no cycle, and adding any edge creates exactly one cycle.

The magic number is n - 1. A connected graph needs at least n - 1 edges, and a graph with no cycles can have at most n - 1 edges. A tree sits exactly where both limits meet. For a forest with c components the edge count is n - c.

Python Is this graph a tree?

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the last two answers: the third graph has 3 edges on 4 vertices (n - 1) but they form a triangle plus an isolated vertex: a cycle, so not a tree. The fourth has 4 edges for 5 vertices but is disconnected for the same reason.

Leaves

Every tree with at least 2 vertices has at least two leaves (vertices of degree 1): look at the two ends of a longest path. Deleting a leaf from a tree leaves a smaller tree, which is the engine of many inductive proofs. Counting degrees with the handshake lemma gives sum of deg = 2(n - 1), so the average degree is just under 2.

Python Leaves and degree sum

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rooted trees

Pick one vertex as the root and orient everything away from it. Now each vertex except the root has a unique parent, and its other neighbors are children. The depth of a vertex is its distance from the root, and the height of the tree is the largest depth. Vertices with no children are leaves. Computing parents and depths is just a BFS from the root.

Python Parents, depths and subtree sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reverse-BFS-order loop is a standard trick: process children before their parents to accumulate sums, counts or maxima up the tree.

Diameter and center

The diameter of a tree is the length of its longest path. A beautiful two-pass algorithm finds it: BFS from any vertex to find the farthest vertex a, then BFS from a; the farthest vertex b from a gives the diameter d(a, b). The center of a tree is the middle vertex (or two adjacent vertices) of that longest path. Trees have one or two centers, found also by repeatedly stripping all leaves.

Python Diameter and center of a tree

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why trees matter

Trees appear everywhere because they are the minimal connected structure. Next we choose a tree inside a bigger graph (a spanning tree) in the minimum spanning trees lesson, and later we count labeled trees with PrΓΌfer codes.

Common mistakes

  • Thinking a tree must be drawn with a root at the top: a tree is just a connected acyclic graph.
  • Forgetting that n - 1 edges alone does not make a tree; the graph must also be connected (or acyclic).
  • Confusing forest and tree: every tree is a forest, but a forest may be disconnected.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. A connected graph has 12 vertices and 11 edges. What is it?

    Connected with n - 1 edges is one of the equivalent definitions of a tree.
  2. 2. How many edges does a forest with 20 vertices and 4 components have?

    A forest with c components has n - c edges: 20 - 4 = 16.
  3. 3. In a tree, how many different paths join two given vertices?

    Two different paths would form a cycle, which trees do not have, and connectivity guarantees at least one.
  4. 4. What is the minimum number of leaves in a tree with at least two vertices?

    The two ends of a longest path are leaves.

Summary

  • A tree is a connected acyclic graph; a forest is a graph whose components are trees.
  • A tree on n vertices has n - 1 edges, unique paths between vertices and at least two leaves.
  • Connected plus n - 1 edges, or acyclic plus n - 1 edges, each suffice.
  • Rooting a tree gives parents, children, depth and height; a BFS computes them.
  • Diameter and center follow from two BFS runs.

Next: Minimum Spanning Trees