1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Can you state how, for a parent $u$, $d[v]$ of all its children $v$ relates to $d[u]$? What about $h(u)$? Can you give an algorithm using less additional storage than your first stab? $\endgroup$
    – greybeard
    Dec 7 '21 at 16:37
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.