Trees

A tree is a structure made of nodes (points) connected by edges (lines).

Example tree

What makes it a tree

A graph is a tree if it satisfies both:

1. Connected: you can reach every node from any other node through the edges.
2. No cycles: you cannot start at a node, follow edges, and come back to the same node without repeating edges.

A very useful equivalent rule:

• Between any two nodes, there is exactly one simple path.

This “unique path” property is the main reason trees show up everywhere in problem solving.

Important facts

Number of edges

If a tree has n nodes, it has exactly:

• n - 1 edges

Adding/removing edges

Add one edge → creates a cycle

In a tree, there’s exactly one path between any two nodes u and v.

If you add a new edge (u, v):

• the old path from u to v still exists
• plus the new direct edge

So you now have a loop: (old path u→v) + (new edge v→u) → that’s a cycle. It’s exactly one cycle because the old u↔︎v path in a tree is unique.

Remove one edge → becomes disconnected

Every edge in a tree is a bridge. If you remove an edge (u, v):

• there is no other route between u and v (otherwise a cycle would have existed)
• so the tree splits into two separate components (two parts).

Rooting a tree

Trees are often given with undirected edges (both directions). To make many problems easier, we choose one node as a root.

Once you choose a root:

• Every node (except the root) has exactly one parent (the neighbor closer to the root).
• A node may have multiple children (neighbors farther from the root).
• depth[v] = how many edges from the root to v.
• subtree(v) = v and everything under it (its descendants).

Rooting does not change the tree itself. It only gives it a direction and a “family structure” for reasoning.

Representing a tree in code

We’ll assume:

int n;                          // nodes are 0..n-1
vector<int> g[n];       // adjacency list

Each g[v] contains all neighbors of node v.

Build parent and depth with DFS

vector<int> parent(n, -1), depth(n, 0);

void dfs(int v, int p) {
    parent[v] = p;
    for (int to : g[v]) {
        if (to == p) continue;
        depth[to] = depth[v] + 1;
        dfs(to, v);
    }
}

What this gives you

• parent[v]: the node above v in the rooted tree
• depth[v]: distance from the root

Subtree size

sub[v] = number of nodes in the subtree of v (including v).

vector<int> sub(n, 1);

void dfs_subtree(int v, int p) {
    sub[v] = 1;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs_subtree(to, v);
        sub[v] += sub[to];
    }
}

Common uses:

• count how big a branch is
• compute how many pairs or paths “go through” an edge

Quick summary

• Tree = connected, no cycles
• Unique path between any two nodes
• n nodes ⇒ n-1 edges
• Pick a root to define parent/children/depth/subtree
• DFS builds parent/depth/subtree sizes