5. Tree algorithms

This chapter discusses algorithms for processing trees, which are graphs that are both connected and acyclic. Such graphs have special properties that make them easier to process than general graphs. We focus on two basic techniques: rooting the tree and finding ancestors efficiently.

Basics of trees

A tree is an undirected graph that is both connected and acyclic. For example, here is a tree that consists of \(6\) nodes:

Here are some properties and terms related to trees:

A tree of \(n\) nodes always has \(n-1\) edges. For example, the tree above has \(6\) nodes and \(5\) edges.
If we remove any edge from a tree, the graph is no longer a tree because it will have more than one component and will not be connected anymore.
If we add any edge to a tree, the graph is no longer a tree because it will have a cycle and will not be acyclic anymore.
The leaves of a tree are the nodes whose degree is \(1\), meaning that they are connected to exactly one other node. For example, the leaves in the tree above are nodes \(3\), \(4\), \(5\), and \(6\).
There is a single shortest path between any two nodes in a tree. In the tree above, the shortest path between node \(1\) and node \(5\) is \(1-2-5\).
The distance between two nodes in a tree is the number of edges in the shortest path between them. In the tree above, the distance between nodes \(1\) and \(5\) is \(2\).

Note that when we define a tree as above, the tree has no hierarchy. That is, there is no root node, and the nodes do not have children. According to the definition, any undirected graph that is both connected and acyclic is a tree.

A convenient way to store a tree in C++ is to use a vector of vectors to represent the adjacency list of the graph. For example, the following code defines the tree shown above:

vector<vector<int>> tree(6+1);

tree[1].push_back(2);
tree[1].push_back(3);
tree[1].push_back(4);
tree[2].push_back(1);
tree[2].push_back(5);
tree[2].push_back(6);
tree[3].push_back(1);
tree[4].push_back(1);
tree[5].push_back(2);
tree[6].push_back(2);

Rooting the tree

Even if we work with trees that do not have a root node, it is often useful to root the tree by choosing one of the nodes as the root. After that, we can conveniently use recursion and other techniques to process the tree.

As an example, consider the problem of coloring the tree nodes so that each node is either black or white, no two adjacent nodes are black, and the number of black nodes is as large as possible. For example, the optimal coloring in the tree

is to color nodes \(1\) and \(2\) white and nodes \(3\), \(4\), \(5\), and \(6\) black, which gives a coloring with four black nodes. To find such a coloring, we can use a recursive algorithm that works for a rooted tree. First, choose any node and appoint it as the root of the tree. For example, let’s choose node \(1\) as the root:

Then, we can calculate, for each node \(x\), two values:

The maximum number of black nodes in the subtree of node \(x\) assuming that node \(x\) is white.
The maximum number of black nodes in the subtree of node \(x\) assuming that node \(x\) is black.

The following code shows how we can calculate the maximum number of black nodes in practice. The function is given three parameters: node is the current node, parent is its parent node, and color is \(0\) (white) or \(1\) (black).

int max_black_nodes(int node, int parent, int color) {
    int count = 0;
    if (color == 1) count = 1;
    for (auto child : graph[node]) {
        if (child == parent) continue;
        if (color == 0) {
            count += max(max_black_nodes(child, node, 0),
                         max_black_nodes(child, node, 1));
        }
        if (color == 1) {
            count += max_black_nodes(child, node, 0);
        }
    }
    return count;
}

The loop goes through all children of the current node. The parameter parent is used to make sure that the parent of the node is not considered as a child node. If the color of the node is white, the color of its child can be white or black. If the color of the node is black, the color of its child can only be white.

To calculate the number of black nodes in the optimal coloring, we can take the maximum of max_black_nodes(1, 0, 0) and max_black_nodes(1, 0, 1), where \(1\) is the appointed root node. The value \(0\) for the parent means that the root node does not have a parent. We take the maximum of the two values because the color of the root node can be either black or white.

To speed up the algorithm, we can use dynamic programming and store the result of the function for each combination of node and color, a total of \(2n\) combinations where \(n\) is the number of nodes. Thus, we can find the maximum number of black nodes in a coloring in \(O(n)\) time.

Tree diameter

The diameter of a tree is the maximum distance between any two nodes in the tree. For example, the diameter of the tree

is \(3\) because we can choose two nodes (such as \(3\) and \(5\)) whose distance is \(3\), but it is not possible to choose two nodes with distance \(4\).

To calculate the diameter of a tree, it is useful to root the tree first:

The diameter always corresponds to a path between two leaves. We can represent such a path by combining two paths: first going upwards from a leaf to an intermediate node, then downwards to another leaf. For example, the tree above contains the following path from node \(3\) to node \(5\), where node \(1\) is the intermediate node:

Go from node \(3\) upwards to node \(1\) (length \(1\)).
Go from node \(1\) downwards to node \(5\) (length \(2\)).

The length of this path is \(1+2=3\), which is the distance between nodes \(3\) and \(5\). This is the diameter of the tree because there are no two leaves whose distance is greater than \(3\).

We can calculate, for each node \(x\), the maximum length of such a path where node \(x\) is the intermediate node. To do that, it is enough to calculate the length of the longest path and the length of the second longest path from node \(x\) downwards to a leaf. In the tree above, we calculate the following values:

Node	Longest path length	Second longest path length
\(1\)	\(2\)	\(1\)
\(2\)	\(1\)	\(1\)
\(3\)	\(0\)	\(0\)
\(4\)	\(0\)	\(0\)
\(5\)	\(0\)	\(0\)
\(6\)	\(0\)	\(0\)

Then, we choose the node where the sum of the two path lengths is maximum. In this case, we choose node \(1\), where the sum is \(2+1=3\). We can calculate the longest and second longest path length in \(O(n)\) time, which gives an algorithm for calculating the diameter in \(O(n)\) time.

Surprisingly, we can also use the following approach to find the diameter of a tree in \(O(n)\) time: first choose any node \(a\), then find the furthest node from \(a\) (call it \(b\)), and finally find the furthest node from \(b\) (call it \(c\)). The diameter of the tree is the distance between nodes \(b\) and \(c\). For example, in the tree above, we can select \(a=1\), \(b=5\), and \(c=3\), which gives the correct result. Can you prove why this algorithm works?

Finding ancestors

The \(k\)th ancestor of node \(x\) in a rooted tree, \(\textrm{ancestor}(x,k)\), is the node that we reach if we go \(k\) steps upwards from node \(x\). For example, in the following tree, \(\textrm{ancestor}(2,1)=1\) and \(\textrm{ancestor}(8,2)=4\).

It turns out that we can calculate any ancestor in \(O(\log n)\) time after preprocessing the tree. The idea is to precalculate all values of \(\textrm{ancestor}(x,2^b)\), where \(x\) is a node in the tree and \(b\) is an integer between \(0\) and \(\lfloor \log_2 n \rfloor\).

First, \(\textrm{ancestor}(x,2^0)\) is the parent of node \(x\). Then, we can use the following recursive formula to calculate the other ancestors in \(O(n \log n)\) time:

\[\textrm{ancestor}(x,2^b)=\textrm{ancestor}(\textrm{ancestor}(x,2^{b-1}),2^{b-1})\]

After preprocessing, we can calculate any value of \(\textrm{ancestor}(x,k)\) by representing \(k\) as a sum of powers of two. For example, the representation for \(k=42\) is \(2^5+2^3+2^1=42\). Thus,

\[\textrm{ancestor}(x,42)=\textrm{ancestor}(\textrm{ancestor}(\textrm{ancestor}(x,2^5),2^3),2^1).\]

The representation of a number \(k\) always consists of \(O(\log k)\) powers of two, so we can calculate any value of \(\textrm{ancestor}(x,k)\) in \(O(\log n)\) time.

In practice, we can create an array levelup so that levelup[x][b] contains the value of \(\textrm{ancestor}(x,2^b)\). We can fill the array as follows:

for (int x = 1; x <= n; x++) {
    levelup[x][0] = parent[x];
}
for (int b = 1; b <= logn; b++) {
    for (int x = 1; x <= n; x++) {
        levelup[x][b] = levelup[levelup[x][b-1]][b-1];
    }
}

Here logn is equal to \(\lfloor \log_2 n \rfloor\). Note that we assume if a node \(x\) does not have the \(2^b\)th ancestor, then levelup[x][b] equals \(0\). In particular, levelup[x][0] is \(0\) when \(x\) is the root node.

Now we can find the value of \(\textrm{ancestor}(x,k)\) as follows:

int ancestor(int x, int k) {
    for (int b = logn; b >= 0; b--) {
        if (k & (1 << b)) {
            x = levelup[x][b];
        }
    }
    return x;
}

The idea above is to check the bit positions in \(k\) where the bit is one. This gives the representation of \(k\) as a sum of powers of two. For example, the bit representation of \(42\) is \(101010\), and the one bit positions are \(5\), \(3\) and \(1\) (zero-indexed from right to left). Thus, we move upwards three times using the levelup array.

Lowest common ancestors

The lowest common ancestor of nodes \(a\) and \(b\) in a rooted tree is the lowest node that is an ancestor of both \(a\) and \(b\). For example, in the following tree, node \(2\) is the lowest common ancestor of nodes \(5\) and \(8\).

We can find the lowest common ancestor of nodes \(a\) and \(b\) using the ancestor function we discussed earlier. To do that, we calculate the depth of each node, which is the number of edges from the root to that node. In the above tree, the depth of node \(5\) is \(2\) and the depth of node \(8\) is \(3\).

We first align the two nodes \(a\) and \(b\) to the same level. If one node is deeper, we move it upwards using the ancestor function until both nodes are at the same depth. After that, we find the lowest common ancestor by moving both nodes upwards together until they meet.

In practice, we can calculate the lowest common ancestor as follows:

int lca(int a, int b) {
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    b = ancestor(b, depth[b] - depth[a]);
    if (a == b) return a;

    for (int k = logn; k >= 0; k--) {
        if (levelup[a][k] != levelup[b][k]) {
            a = levelup[a][k];
            b = levelup[b][k];
        }
    }
    return parent[a];
}

The first part aligns the nodes to the same level. First, we make sure that the depth of \(a\) is not greater than the depth of \(b\), and then move \(b\) upwards using the ancestor function. If \(a=b\) after this, we have already found the lowest common ancestor.

The second part goes through the powers of two in decreasing order and moves both nodes \(a\) and \(b\) upwards if they do not meet. Finally, the lowest common ancestor is the parent of \(a\) (which is the same as the parent of \(b\)).

This method is efficient because each upward step takes \(O(\log n)\) time due to our preprocessing. Thus, the overall time complexity to find the lowest common ancestor of two nodes is also \(O(\log n)\).