Trees: Terms, Traversal, Subtrees and Diameter

Lesson 5 of 17 · Graphs and trees

A tree is a connected graph without cycles. A family tree, the folder structure on a computer and the organisation of a school are trees. Because of their special shape, many tasks on trees are solved with a single traversal: depths, subtree sizes, the diameter.

Before you start: prerequisites – BFS and DFS, recursion.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

What is a tree?

A graph with n vertices is a tree if any of these holds (they are all equivalent): it is connected and has no cycle; it is connected and has exactly n − 1 edges; there is exactly one path between every two vertices.

          1            depth 0
        / | \
       2  3  4         depth 1
      / \     \
     5   6     7       depth 2
                \
                 8     depth 3
TermMeaningIn the example
rootthe chosen starting vertex1
parent, childa neighbour closer to the root / farther from the rootthe parent of vertex 6 is 2; the children of vertex 1 are 2, 3, 4
leafa vertex without children3, 5, 6, 8
depththe number of edges from the root to the vertexthe depth of vertex 8 is 3
height of the treethe largest depth3
subtree of vertex vv and all the vertices below itthe subtree of vertex 2: {2, 5, 6}

In the programs below this tree is entered as the number of vertices and then its n − 1 edges:

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

Traversing a tree: parents and depths

A tree is given as n − 1 edges. A depth-first traversal (DFS) from the root determines the parent and the depth of every vertex. Instead of a visited array it is enough not to go back to the parent – a tree has no other cycles.

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

vector<vector<int>> graph;
vector<int> parent, depth;

void dfs(int v, int p) {              // p = the parent of vertex v
    parent[v] = p;
    for (int u : graph[v]) {
        if (u == p) continue;         // we do not go back
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
}

int main() {
    int n;
    cin >> n;
    graph.resize(n + 1);
    parent.resize(n + 1);
    depth.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);                        // the root is 1, its "parent" is 0
    for (int v = 1; v <= n; v++)
        cout << v << ": parent " << parent[v] << ", depth " << depth[v] << endl;
    return 0;
}

For the tree from the picture the program prints:

1: parent 0, depth 0
2: parent 1, depth 1
3: parent 1, depth 1
4: parent 1, depth 1
5: parent 2, depth 2
6: parent 2, depth 2
7: parent 4, depth 2
8: parent 7, depth 3
Deep trees: if the tree is a "chain" of 105 or more vertices, the recursion is just as deep. At competitions the stack is usually large enough, but if the program crashes, DFS should be written with its own stack, or BFS should be used.

Subtree size

The size of the subtree of vertex v is 1 (v itself) plus the sum of the sizes of its children's subtrees. The children are processed before the parent, so we calculate the size after the recursive calls (a postorder traversal).

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

vector<vector<int>> graph;
vector<int> subtreeSize;

void dfs(int v, int p) {
    subtreeSize[v] = 1;                   // vertex v itself
    for (int u : graph[v]) {
        if (u == p) continue;
        dfs(u, v);
        subtreeSize[v] += subtreeSize[u]; // add the child's subtree
    }
}

int main() {
    int n;
    cin >> n;
    graph.resize(n + 1);
    subtreeSize.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);
    for (int v = 1; v <= n; v++) cout << subtreeSize[v] << " ";
    cout << endl;
    return 0;
}

For the tree from the picture the program prints 8 3 1 3 1 1 2 1: for example, the subtree of vertex 4 is {4, 7, 8}.

The diameter of a tree

The diameter is the largest distance (the number of edges) between two vertices of the tree. There is a nice trick with two traversals:

  1. from any vertex find the farthest vertex A;
  2. from A find the farthest vertex B;
  3. the distance from A to B is the diameter.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<vector<int>> graph;

// BFS from vertex s; returns the distances of all the vertices from s
vector<int> bfs(int s) {
    vector<int> d(n + 1, -1);
    queue<int> q;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : graph[v])
            if (d[u] == -1) {
                d[u] = d[v] + 1;
                q.push(u);
            }
    }
    return d;
}

int main() {
    cin >> n;
    graph.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> d1 = bfs(1);
    int A = 1;
    for (int v = 1; v <= n; v++) if (d1[v] > d1[A]) A = v;   // the farthest from 1
    vector<int> d2 = bfs(A);
    int B = A;
    for (int v = 1; v <= n; v++) if (d2[v] > d2[B]) B = v;   // the farthest from A
    cout << "diameter = " << d2[B] << endl;
    return 0;
}

In the example the diameter is the path 5 – 2 – 1 – 4 – 7 – 8 of length 5, so the program prints diameter = 5. BFS is used here instead of DFS to avoid deep recursion.

A tree given by an array of parents

A tree is often given differently: for every vertex except the root its parent is given (p[2], p[3], …, p[n]). Then we build the graph by adding a child to every parent: children[p[v]].push_back(v). If p[v] < v always holds, the subtree sizes can also be calculated without recursion – by going from n back to 2: size[p[v]] += size[v].

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

The number of leaves and the height

A tree with n vertices (the root is 1) is given as n − 1 edges. Print the number of leaves and the height of the tree. (n ≥ 2)

Example

Input

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

Output

4 3
TASK 02Difficulty: medium

The largest subtree sum

Every vertex of a tree has a value (it can also be negative). The root is 1. Print the largest sum of the values of some subtree.

Input: n, then n values, then n − 1 edges.

Example

Input

5
3 -10 4 2 2
1 2
1 3
2 4
2 5

Output

4
TASK 03Difficulty: medium

The distance between two vertices

A tree and two vertices a and b are given. Print the number of edges on the path between them and the path itself.

Input: n, n − 1 edges, then a b.

Example

Input

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

Output

5
5 2 1 4 7 8
Common mistakes and tips
  • A tree with n vertices has exactly n − 1 edges – the reading loop goes up to n − 1.
  • In DFS on a tree pass the parent so that you do not go back.
  • Subtree sums can be large – use long long.

Check your knowledge

Open the quiz

Trees

1. How many edges does a tree with 50 vertices have?




2. How many paths are there between two vertices of a tree?




3. When is the subtree size of vertex v calculated?




4. How is the diameter of a tree found?