Algorithmic Problem on Trees

Question

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find the following,

$ d[v] := \max\limits_{w \text{ is a sibling of $v$}} h[w] \qquad \forall v \in V. $

Note: The algorithm I was able to come up is the trivial one.

1. Finds the height of all vertices using DFS.
2. Do a BFS from the root and store all the vertices to a particular distance in a map.
3. Go over the list for every element $v$ and find the maximum using the expression above.

Can we do better than this?

Answer 1

The basic idea in your algorithm is correct (it will result in an optimal algorithm if you implement it correctly)

Hpwever the details are missing. For example, how can one compute the height of the nodes using DFS?

Another important detail is the "mapping" you talked about. How exactly do you store this mapping? The regular approach of using a hashmap will not do the job well enough. You may want to consider storing it as a list of lists (think about it for a minute, it shouldnt be too complicated) instead.

---

Now to the main question - this algorithm is optimal. The runtime of each step is $O(n)$, and thus the entire algorithm takes $O(n)$.

But notice that the problem requires you to output a value for each node - and thus any algorithm will have to spend at least $\Omega(n)$ time printing the output.