Introduction to Trees

A tree is a connected, undirected graph with no cycles. Connected means every pair of vertices can reach one another; acyclic means there is no route that returns to its starting vertex without reusing an edge. These two requirements give trees their most useful feature: there is exactly one simple path between any two vertices. Trees model roads with no alternative routes, organizational hierarchies, directory structures, and connections chosen by a minimum spanning tree algorithm.

This lesson separates the underlying unrooted tree from the extra relationships created by choosing a root. You will also write a program that checks whether an input graph is a tree. This matters because many later algorithms deliberately skip general-graph checks: their correctness relies on the input really being a tree.

Prerequisites: Undirected graphs, adjacency lists, and basic BFS. No earlier tree lessons are required.

Build the idea

1. 1. Recognize a tree by its paths

   Consider edges (1,2), (1,3), (3,4), and (3,5). Every vertex is reachable from 1, and there is no cycle. The only simple path from 2 to 5 is 2 → 1 → 3 → 5. If there were two different simple paths between a pair, follow them to their first divergence and next reunion: their different sections would form a cycle. Conversely, connectivity gives at least one path. Together these facts prove uniqueness.

2. 2. Understand the N−1 edge rule

   A tree with N vertices has exactly N−1 edges. One proof repeatedly removes a leaf, a vertex with one neighbor. A longest path must end at leaves; otherwise it could be extended. Removing one endpoint and its incident edge leaves a smaller tree. Starting from one vertex and zero edges, reversing those removals adds one vertex and one edge each time. After N−1 additions there are N vertices and N−1 edges.

   The count alone is insufficient: a triangle plus an isolated vertex has four vertices and three edges but is not a tree. For an undirected graph, connectivity together with exactly N−1 edges is sufficient. A connected graph needs at least N−1 edges to discover its N vertices. If a cycle existed, removing a cycle edge would keep it connected with fewer than N−1 edges, a contradiction.

3. 3. Choose a root without changing the edges

   Root the example at 1. Vertex 1 has children 2 and 3; vertex 3 has children 4 and 5. The parent of a nonroot vertex is its next vertex on the unique path toward the root. Depth counts edges to the root: depths are 0, 1, 1, 2, 2. A descendant lies below a vertex, and its rooted subtree contains itself and all descendants. Thus the subtree of 3 contains {3,4,5}.

   Degree is the number of undirected neighbors; it does not depend on the root. Children and depth do depend on the root. In an unrooted tree a leaf normally has degree 1, with the one-vertex tree handled separately. In a rooted tree a leaf has no children. A root with one child has degree 1 but is not a rooted leaf. Always state which convention a problem uses.

4. 4. Turn the characterization into a validator

   Read N and M, then store each undirected edge in both adjacency lists. BFS from vertex 1 marks vertices when they enter the queue, so each vertex enters once. The variable reached counts the visited vertices. Print YES exactly when reached equals N and M equals N−1. BFS still terminates on invalid input containing a cycle because it uses a visited array.

   The input contract below requires positive N and valid endpoint labels. Self-loops and duplicate edges cannot cause an incorrect YES: a connected multigraph with N−1 edges has no spare edge for either. The implementation is a validator, not a tree-only traversal, so it deliberately keeps visited[] rather than only ignoring a parent.

5. 5. Use the structure

   Deleting any tree edge splits the tree into two components: a remaining route between its endpoints would contradict unique paths. Adding an edge between two existing distinct vertices creates a cycle consisting of that edge and their existing path. These observations explain why tree generators add each new vertex through exactly one old vertex, and why later subtree algorithms can combine child results without overlapping descendants.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m; // Contract: n >= 1 and endpoints are in 1..n.
    // Store both directions so BFS can follow undirected edges.
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<bool>visited(n+1,false);
    queue<int>q;
    q.push(1);
    visited[1]=true; // Mark on insertion to avoid duplicate queue entries.
    // Connectivity means that this search must reach all n vertices.
    int reached=0;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        ++reached;
        for(int next:graph[v]){
            if(!visited[next]){
                visited[next]=true;
                q.push(next);
            }
        }
    }
    // A connected undirected graph is a tree exactly when m == n-1.
    cout<<(reached==n&&m==n-1?"YES":"NO")<<'\n';
}

Complexity analysis

O(N+M) time and O(N+M) space for a general input graph: each vertex enters BFS once and each edge appears twice in adjacency lists. On a valid tree M=N−1, so both bounds become O(N).

Example input and output

N M, followed by M lines a b describing an undirected graph. N≥1 and all labels are in 1..N. Output YES if it is a tree, otherwise NO.

Input

5 4
1 2
1 3
3 4
3 5

Output

YES

All five vertices are reachable and there are four edges. The unique path from 2 to 5 is 2–1–3–5.

Practical applications

Validate tree input before using specialized algorithms; model hierarchies; reason about unique routes; recognize when a connected structure is a spanning tree. Next, choose a root and compute parent/depth arrays.

Check your understanding

An undirected graph has N vertices and N−1 edges. What additional check makes this a sufficient tree test?

Put it into practice

Modify the validator to print the number of connected components when the answer is NO. Test a single vertex, a triangle plus an isolated vertex, and a path.