Trees

A tree is a connected graph with no cycles, such as a company where every employee has exactly one boss. Rooting it at one vertex gives each vertex a parent, a depth and a subtree, and one depth-first search computes all three in $O(n)$, which answers questions such as how many people work under each boss. For a binary search tree, with a left and a right child per node, see binary search tree.

Explanation

Eight vertices are joined by seven edges, and every vertex can reach every other one: this is a tree. Any tree with $n$ vertices has n - 1 edges and exactly one path between two vertices. For example, the only path from vertex 7 to vertex 6 goes up through vertex 1. A statement may also give it as a list where each vertex but one names its parent.

Rooting a tree

To root the tree, pick one vertex as the root and draw it on top.

Fig. 1. The same edges rooted at vertex 1 (left) and at vertex 2 (right).

The parent of a vertex is the next vertex on its path up to the root, and the vertices right below it are its children. On the left, vertex 2 has parent 1 and children 4 and 5.

The depth of a vertex is the number of edges on its path to the root: 0 for the root, 2 for vertex 5.

The subtree of a vertex is the vertex and everything below it. The subtree of vertex 2 is shaded, and its size is 5.

Rooted at vertex 2, on the right, vertex 1 has parent 2 and depth 1.

Subtree sizes

Depth is easy: one more than the parent's. Subtree size is harder. When each employee names their boss, a first idea is to walk up from every employee to the root, adding 1 at each vertex on the way.

Fig. 2. The walk up from vertex 7 adds 1 at vertices 7, 5, 2 and 1.

The sizes are right, and the walks take 14 steps here, the sum of all depths. But on a chain, where each vertex is the child of the one before, 2 \cdot 10^5 vertices need about 2 \cdot 10^{10} steps, O(n^2): far too slow.

A vertex's subtree is the vertex itself plus the subtrees of its children. Vertex 2, with children 4 and 5, has size 1 + 1 + 3 = 5. So the size of a vertex is known as soon as all its children have theirs.

One search for everything

With edges instead of parents, the program has to find the parents too, and one search does both. A depth-first search, which goes as deep as it can before it comes back up, comes back up from a vertex exactly when all its children are done. So one search from the root sets the depth going down into a vertex and adds a child's size coming back up from it. The search goes down and back up each edge once, so it takes $O(n)$ time. The arrays and the recursion, one unfinished call per vertex on the current path, take $O(n)$ memory.

A tree has no cycles, so the only neighbour of a vertex that the search has already entered is its parent. So the search skips the parent and needs no marks.

Let's run the search from vertex 1.

Nothing is entered yet.

Root it at vertex 1 and enter it: its depth is 0, it has no parent, and its size starts at 1.

Go down from 1 to 2: its depth is 0 + 1 = 1. Enter 2: its parent is 1, and its size starts at 1.

Go down from 2 to 4: its depth is 1 + 1 = 2. Enter 4: its parent is 2, and its size starts at 1.

Vertex 4 has no children. Come back up from 4 to 2: the size of 2 becomes 1 + 1 = 2.

Go down from 2 to 5: its depth is 1 + 1 = 2. Enter 5: its parent is 2, and its size starts at 1.

Go down from 5 to 7: its depth is 2 + 1 = 3. Enter 7: its parent is 5, and its size starts at 1.

Come back up from 7 to 5: the size of 5 becomes 1 + 1 = 2.

Go down from 5 to 8: its depth is 2 + 1 = 3. Enter 8: its parent is 5, and its size starts at 1.

Come back up from 8 to 5: the size of 5 becomes 2 + 1 = 3.

Vertex 5 has no children left. Come back up from 5 to 2: the size of 2 becomes 2 + 3 = 5.

Come back up from 2 to 1: the size of 1 becomes 1 + 5 = 6.

Go down from 1 to 3: its depth is 0 + 1 = 1. Enter 3: its parent is 1, and its size starts at 1.

Go down from 3 to 6: its depth is 1 + 1 = 2. Enter 6: its parent is 3, and its size starts at 1.

Come back up from 6 to 3: the size of 3 becomes 1 + 1 = 2.

Come back up from 3 to 1: the size of 1 becomes 6 + 2 = 8, the whole tree.

1/16

Fig. 3. Step through the search with the buttons or the arrow keys. Light blue vertices are on the current path, green ones are done.

In C++

In code, par[v], dep[v] and sz[v] belong to vertex v, and adj is the adjacency list with both directions of each edge. dfs(v, p) enters v, whose parent is p. Code before the call dfs(u, v) runs on the way down, code after it on the way back up. The root's parent is 0, which is no vertex, so the root skips no neighbour.

The program reads n and n - 1 edges a b, roots the tree at vertex 1 and prints v par[v] dep[v] sz[v] for every vertex. For the 8-vertex tree the input is:

8
1 2
3 1
4 2
2 5
6 3
5 7
8 5

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> par, dep, sz;

void dfs(int v, int p) {
    // enter v
    par[v] = p;
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u == p) continue;   // skip the parent
        // go down
        dep[u] = dep[v] + 1;
        dfs(u, v);
        // come back up
        sz[v] += sz[u];
    }
}

int main() {
    int n;
    cin >> n;
    adj.assign(n + 1, {});
    par.assign(n + 1, 0);
    dep.assign(n + 1, 0);
    sz.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    // root it
    int root = 1;
    dep[root] = 0;
    dfs(root, 0);

    for (int v = 1; v <= n; v++)
        cout << v << ' ' << par[v] << ' ' << dep[v] << ' ' << sz[v] << '\n';
}

Counting subordinates

When the input lists each employee's boss p_2, \ldots, p_n, employee v has sz[v] - 1 subordinates. The parents are given, so an edge from boss to employee is enough. For 2 \cdot 10^5 employees, use the loop from the warning above.

for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    adj[p].push_back(i);   // only from the boss to the employee
}
dfs(1, 0);
for (int v = 1; v <= n; v++) cout << sz[v] - 1 << ' ';

Cutting an edge

Removing the edge between v and par[v] leaves sz[v] vertices on the side of v and n - sz[v] on the other. Two vertices on different sides have this edge on their path, so sz[v] * (n - sz[v]) pairs of vertices use it: 3 · 5 = 15 pairs for the edge 2–5.

Fig. 4. Any path from a blue vertex to a white one crosses the cut edge 2–5.

for (int v = 2; v <= n; v++)   // the edge from v to par[v]
    cout << sz[v] << ' ' << n - sz[v] << ' ' << (long long)sz[v] * (n - sz[v]) << '\n';

Passing a value down

A value that depends only on the path from the root is set like depth, before the call. For example, if some vertices are marked (mark[u] is 1), cnt[u] counts the marked vertices on the path from the root to u. If vertices 1, 2 and 5 are marked, cnt[7] is 3.

// go down
dep[u] = dep[v] + 1;
cnt[u] = cnt[v] + mark[u];
dfs(u, v);

Before the first call, set cnt[root] = mark[root].

Common mistakes

• Reading the first number of an edge as the parent. The edge 3 1 above would make vertex 3 the parent of the root.

• Running one search when the input is several separate trees. On 5 vertices with edges 1–2, 3–4 and 4–5, a search from vertex 1 leaves vertices 3, 4 and 5 with size 0. Start a search from every vertex whose sz[v] is still 0.

• Printing dep[v] when the statement puts the root on level 1. Vertex 7 of the 8-vertex tree is then on level 4, while dep[7] is 3. Print dep[v] + 1.

Similar techniques

Depth-first search works on any graph; on a tree, skipping the parent replaces its marked array.

Breadth-first search from the root reaches vertices in order of depth.

Dynamic programming on trees uses the "come back up" step with another rule in place of the sum.

Lowest common ancestor uses par and dep to find the deepest vertex above two given vertices.

Tree diameter, the longest path in a tree, uses dep from two searches.

A binary search tree is a data structure; many problems titled "Tree" are about it.

Practice