Trees, traversal and recursive structures

One route between two rooms

Seven rooms A,B,C,D,E,F,G are connected by passages AB, AC, BD, BE, CF and FG. To get from D to G without revisiting a room, go D,B,A,C,F,G. That route uses five passages. There is no second route unless you add a passage or revisit part of the journey.

Draw the rooms as labelled vertices and passages as edges. The exact edge inventory matters; the drawn lengths do not represent walking distance. This connected network has no cycle, so it is a tree. Predict what adding the missing passage DG changes before reading the proof.

State exactly what counts as a tree

Counting, zero and natural numbers prepares the vertex and edge counts; Addition and subtraction prepares the formulas; Examples, explanations and counterexamples prepares the difference between an example and a proof. All graph and recursive terms needed here are defined locally. On a first reading, follow the room example and visit orders, then return to the unique-path and recursive proofs.

This lesson uses finite undirected simple graphs. Their vertex labels are distinct. An edge joins two different vertices, has no direction, and appears at most once. Thus loops and parallel edges are excluded. The degree of a vertex is its number of neighbours.

A path is a sequence of distinct vertices with an edge between every consecutive pair. Its length is the number of those edges. The one-vertex sequence is a path of length zero. A cycle is a closed sequence of at least three edges whose vertices are distinct except for its repeated start and end.

A graph is connected here when it has at least one vertex and a path joins every pair. A tree is a connected graph with no cycle. A forest is any graph with no cycle; it may be disconnected, contain isolated vertices or have no vertices. A component is a maximal group of mutually connected vertices. The empty forest has zero components.

Write n for the number of vertices, e for the number of edges and c for the number of components. A one-vertex graph with no edge is a tree. The empty graph is a forest but is not a tree under the stated nonempty convention.

A tree supplies exactly one path

Let T be a tree and choose different vertices u,v. Connectedness supplies at least one path. Suppose two different paths exist. Follow their shared initial part to the vertex where they first separate. Follow the second path until it first returns to a vertex of the first path; it must return by v. Since paths have no repeated vertices, that return cannot be to the earlier shared prefix.

Between the separation and return vertices, the second path has no interior vertex on the first path. Its segment and the first path’s segment therefore form a cycle, contradicting the tree condition. Thus the path is unique. A path from a vertex to itself is uniquely the zero-length path under our definition.

Conversely, suppose a nonempty finite simple graph has exactly one path between every two different vertices. It is connected because those paths exist. A cycle would provide two distinct routes around it between two of its vertices, contradicting uniqueness. Therefore the graph is a tree. The nonempty condition is necessary: the empty graph has no pair to test but is not a tree here.

In a forest, vertices in one component have exactly one path, while vertices in different components have none. The same two-path argument rules out two paths in an acyclic graph; connectedness of each component supplies the existing one.

Remove a leaf to count the edges

An undirected leaf is a vertex of degree one. Every finite tree with at least two vertices has at least two leaves. To prove this, choose a path of greatest possible length; one exists because the graph is finite. Each endpoint has its neighbour on the path. An additional neighbour on the path would make a cycle; an additional neighbour outside it would extend the path. Both are impossible, so both endpoints have degree one.

Delete one leaf and its only edge. At least one vertex remains. A path between two remaining vertices cannot use the deleted leaf as an interior vertex, since that would require two incident edges there. Their original unique path therefore survives. No deletion creates a cycle, so the remaining graph is again a tree.

Repeat until one vertex remains. Each deletion removes exactly one vertex and one edge. Starting with n vertices requires n−1 deletions; the final singleton has zero edges. Therefore every tree has e = n−1. This argument terminates because the positive vertex count decreases at each step, and the leaf argument applies whenever at least two vertices remain.

Each component of a forest is a tree. If its component sizes are n₁,…,n_c, the edge counts are n₁−1,…,n_c−1. Their sum is e = n−c because the components partition all vertices. This includes the empty forest: n = c = e = 0.

The count e = n−1 alone does not prove a graph is a tree. A triangle plus an isolated vertex has n = 4,e = 3, but it has a cycle and is disconnected. For a connected simple graph, however, e = n−1 does imply a tree: delete cycle edges while preserving connectedness until a spanning tree remains. That tree already needs n−1 edges, so a graph with only n−1 cannot have lost any. The next section justifies the deletion step.

One edge changes connectivity or creates one cycle

Remove an edge uv from a tree. If u,v remained connected, a surviving path together with uv would have formed a cycle in the original tree. Thus they are separated. Every vertex belongs to one of their two resulting components: its original path to u either avoids uv, or reaches v before using uv. Hence the result has exactly two components. Each is acyclic and connected, so each is a tree.

Add one missing edge uv to a tree. The original unique path from u to v and the new edge form a cycle. Any cycle in the enlarged graph must use the new edge, because the original tree had none. Removing that edge from such a cycle leaves a path from u to v in the original tree; uniqueness forces it to be the same path. Exactly one cycle was created. Adding a duplicate edge is excluded by the simple-graph convention.

A spanning tree of a connected graph is a subgraph using all its vertices that is itself a tree. If a connected finite simple graph has a cycle, delete an edge of that cycle. The other part of the cycle still joins its endpoints, so any route using the deleted edge can be replaced by a walk using the other cycle edges. Remove repeated-vertex portions of that walk to obtain a path. Connectedness survives.

Continue deleting cycle edges. The finite edge count decreases, so the process stops at a connected acyclic graph with every original vertex: a spanning tree. Different choices can give different spanning trees. This lesson uses unweighted edges and makes no claim that a particular spanning tree minimises a cost.

A root turns routes into parent and child relationships

Choose one vertex as the root. The parent of any other vertex is the preceding vertex on its unique path from the root. The root has no parent. Children of v are the vertices whose parent is v. Depth is the number of edges from the root to the vertex. Every edge joins a parent and a child: otherwise the two root paths and that edge would create a cycle.

A descendant of v is a different vertex whose root path passes through v. The subtree rooted at v consists of v and all its descendants, with their connecting edges. A rooted leaf has no children. In a tree with at least two vertices, a nonroot vertex is a rooted leaf exactly when it has degree one. A degree-one root has a child and is not a rooted leaf. The singleton root has no children, so it is a rooted leaf although its degree is zero.

With A as root, its children are B,C; B has D,E; C has F; F has G. Depths are A:0, B,C:1, D,E,F:2, G:3. If D becomes the root, B is its child, and A becomes B’s child. The undirected edges and degrees have not changed.

A root does not choose an order among siblings. We use the vertex inventory A,B,C,D,E,F,G to order neighbours and children. This extra convention makes the traversal examples deterministic. A different child order may give a different preorder or postorder while preserving the same rooted tree.

Breadth-first visits use a queue

A queue removes the earliest item still waiting: first in, first out. Mark the root discovered and put it in the queue. Remove the front vertex, visit it, and append each undiscovered neighbour in inventory order, marking it when appended. Continue until the queue is empty. Marking on discovery prevents a vertex from being scheduled twice.

For the room tree rooted at A, the visit order is A,B,C,D,E,F,G. After A is visited, B,C wait. Visiting B appends D,E after C; visiting C appends F after D,E. Visiting F eventually appends G. Thus visits proceed by depths 0,1,2,3.

Why do levels stay in order? Initially the queue contains only depth zero. Processing a vertex of depth k appends its children of depth k+1 behind all already waiting vertices. All depth-k vertices are therefore removed before any depth-(k+1) vertex; those children are exactly the next level because every nonroot tree vertex has one parent. This proves the level order for any finite rooted tree.

In a general graph, assign the root level 0 and each newly discovered neighbour the current vertex’s level plus 1. The same queue rule processes assigned levels in nondecreasing order: neighbours newly discovered from level k are appended at level k+1 behind all vertices already waiting. Each assigned level supplies a route of that many edges, so it cannot be less than the minimum path length. For the reverse inequality, argue successively by minimum distance: a vertex at distance d has a predecessor at distance d−1 on a shortest path. That predecessor is processed before levels above d−1, so the vertex is discovered at a level at most d. The base case is the root. Thus the assigned level equals the minimum edge count. The same argument reaches every vertex in the root’s component; no traversal edge can leave that component. A disconnected graph needs a new undiscovered root for each remaining component. Geometric lengths in these drawings are not edge weights.

Depth-first visits and the actual walk are different

To traverse a rooted tree in preorder, visit its root, then traverse each child subtree in the stated order. In postorder, traverse the child subtrees first, then visit the root. Recursion means applying the same procedure to a smaller subtree. A leaf has no child call, so the procedure finishes there. Every call is to a strictly smaller finite subtree, so the process terminates.

With root A and inventory order, preorder is A,B,D,E,C,F,G. Postorder is D,E,B,G,F,C,A. Each vertex is visited exactly once because child subtrees are disjoint and, together with their parent, contain exactly its subtree. Preorder places every ancestor before its descendants; postorder places every descendant before its ancestor.

Neither list is necessarily a graph path. D and E are consecutive preorder entries but are not adjacent. An actual depth-first edge walk returns along a parent edge after finishing each child. Here it is A,B,D,B,E,B,A,C,F,G,F,C,A. Vertices repeat, so it is a walk, not a path.

That full walk crosses each tree edge once into its child subtree and once back. There are e = n−1 edges, so it has 2(n−1) edge moves; the example has 12. This count refers to a complete walk returning to the root, not to a search that stops early. In a general graph, keep a discovered set to avoid cycling; recursive calls follow discovery edges rather than repeatedly following all neighbours.

Combine disjoint child subtrees

Define S(v) as the number of vertices in the subtree rooted at v, including v. Define H(v) as the greatest number of edges from v to a rooted leaf in that subtree. A leaf has S(v) = 1 and H(v) = 0.

For any vertex v, S(v) = 1+Σ S(w), where the sum runs over its children w. The symbol Σ means add one term for every stated child; the sum over no children is zero. The child subtrees have no shared vertex: sharing one would give that vertex two different paths back to v. Every descendant lies in exactly one of those child subtrees. This proves the size formula without double counting.

For a nonleaf, H(v) = 1+max H(w), with the maximum taken over its children. Every route to a descendant leaf first uses one child edge, then a route in that child subtree; choosing the tallest child gives the greatest length. The maximum of an empty list is not used: the leaf case is defined separately.

In the room tree rooted at A, B’s subtree has size 3 and height 1; C’s has size 3 and height 2. Therefore S(A) = 1+3+3 = 7 and H(A) = 1+max(1,2) = 3. F has size 2 and height 1. Postorder computes each child result before it is needed by its parent.

A structure with a shared child is not this rooted tree model. Counting both child substructures may count the shared object twice. A cycle can make an unchecked recursive procedure return to a call that is still unfinished. The disjoint-subtree and decreasing-size arguments explain why the tree assumptions matter.

An expression supplies meaning to an ordered tree

The expression (2+3)·(7−4) has multiplication at its root, addition as the left child and subtraction as the right child. Number leaves hold their own values. An operator node combines the values of its ordered children. The left-right order matters for subtraction: 7−4 = 3, while 4−7 = −3.

Postorder reads 2,3,+,7,4,−,×. Evaluate 2+3 = 5 and 7−4 = 3 before multiplying 5·3 = 15. This is recursive evaluation: each result is proved correct by the already computed children and the operator’s definition. The finite tree ensures termination, and the local arithmetic specifies the result.

An ordered binary tree has at most two children in designated left and right positions. Our earlier size and height formulas allow any number of children. Inorder is a further traversal for ordered binary trees, not an order automatically attached to every undirected tree.

Make a prediction and check the complete record

Compare the unique path, added edge and removed edge cases. Then change the root or reveal visit prefixes. The complete tables retain the actual edge inventory, components and rooted structure so that a drawing cannot silently add a connection.

For recursive cases, predict the selected subtree’s size and height before revealing it. For the expression, predict the selected operator’s value and keep its children in order. A finite model illustrates the general proofs above; checking every supplied case alone would not prove a theorem for every tree.

Worked examples

Try it yourself

1. Classify a singleton with no edges and a graph with no vertices under this lesson’s conventions.

   Show the answer and reasoning

   The singleton is a tree and a forest. The empty graph is a forest but is not a tree.

   The singleton is nonempty, connected and acyclic. The empty graph is acyclic but fails the explicit nonempty connectedness condition; it has zero components.

2. A simple graph has four vertices and three edges. Must it be a tree?

   Show the answer and reasoning

   No. A triangle plus an isolated vertex has those counts.

   It has a cycle and two components. The formula e = n−1 follows from being a tree, but without connectedness the formula alone does not imply one.

3. A finite forest has 12 vertices and four components. How many edges does it have?

   Show the answer and reasoning

   It has 12−4 = 8 edges.

   Each nonempty component with nᵢ vertices has nᵢ−1 edges. Summing subtracts one for each of the four components, including any isolated singleton.

4. If one edge joins vertices in two different components of a forest, does it create a cycle? What changes in the counts?

   Show the answer and reasoning

   It creates no cycle; the component count drops by one and the edge count rises by one.

   A cycle using the new edge would require a previously existing path between its endpoints, but they were in different components. The merged component is a tree; the forest formula still holds.

5. Which cycle appears when DE is added to the room tree?

   Show the answer and reasoning

   D,B,E,D is the unique new cycle, with three edges.

   The original D-to-E path is D,B,E. The new edge closes that path. The unique-path argument rules out any different cycle.

6. If D is the root of the room tree, is D a rooted leaf? Is it an undirected leaf?

   Show the answer and reasoning

   D is an undirected leaf but is not a rooted leaf.

   Its undirected degree remains one. Its neighbour B becomes its child, so it has a child. The two leaf definitions use different conditions.

7. Why is A,B,D,E,C,F,G not a graph path in the room tree?

   Show the answer and reasoning

   Consecutive entries D,E are not connected by an edge; neither are E,C.

   This is a preorder list of visits. The actual walk backtracks through B and A between those child subtrees, and consequently repeats vertices.

8. Could A appear before G in a postorder traversal of the room tree rooted at A?

   Show the answer and reasoning

   No. G is a descendant of A and must be visited first.

   Postorder finishes every child subtree before visiting its parent. Applying that rule along G,F,C,A forces G before A, regardless of sibling order.

9. A tree has nine vertices. How many edge moves does a complete depth-first walk make when it returns to its starting root?

   Show the answer and reasoning

   It makes 2(9−1) = 16 edge moves.

   The tree has eight edges. The complete walk crosses each once towards its child subtree and once back. This is not the number of first visits, which is nine.

10. A vertex has child subtrees of sizes 2,4,1 and heights 1,2,0. Find its subtree size and height.

    Show the answer and reasoning

    Its size is 1+2+4+1 = 8 and its height is 1+max(1,2,0) = 3.

    The parent counts once and disjoint child sizes add. Height follows the longest child branch rather than adding all heights.

11. What happens to the expression value if the subtraction node’s children 7 and 4 are exchanged?

    Show the answer and reasoning

    The new value is (2+3)·(4−7) = −15.

    The subtraction subtree changes from 3 to −3; multiplication then gives 5·(−3). An unordered drawing cannot specify a noncommutative operator’s child order.

What to carry forward

• A tree is a nonempty finite connected acyclic simple undirected graph, equivalently a nonempty finite simple undirected graph with exactly one path between each pair of different vertices.
• A tree has e = n−1 edges; a forest with c components has e = n−c. The edge count alone does not prove a tree.
• Deleting a tree edge creates two components; adding a missing edge creates exactly one cycle.
• A root defines parents, depths and subtrees, while an additional child order makes traversal sequences deterministic.
• Breadth-first visits use a queue and proceed by depth. Preorder visits a parent first; postorder visits it after its descendants.
• A visit list need not be a graph path. A complete returning depth-first walk traverses each edge twice.
• Disjoint child subtrees justify recursive size, height and ordered expression evaluation; a shared child or cycle changes the reasoning.