You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. By convention, $p(r) = r$.

For $k > 1$, define $p^k(v) = p^{k−1}(p(v))$ and $p^1(v) = p(v)$ (so $p^k(v)$ is the $k$-th ancestor of $v$).

Each vertex $v$ of the tree has an associated non-negative integer label $l(v)$. Give a linear-time algorithm to update the labels of all the vertices in T according to the following rule: $$l_{new}(v) = l(p^{l(v)}(v)).$$

This is problem 3.20 in Dasgupta's Algorithm.

My thoughts so far:

  1. The problem comes down to how you find the $l(v)$-th parent of a node $v$, for all $v \in V$, in linear time.

  2. Since chapter 3 is about depth first search, I'm trying to use it. The only way to get the parent once we have the child is to do something in the post-visit routine

      v.visited = true
      for all u adjacent to v:
        if u.visited == false:
  3. If $l(v) = 3$ then somehow we need to send this information up 3 levels in the recursion. But depth first search only moves one level at a time. I don't know how we can preserve the information across multiple calls.

  • $\begingroup$ Remember to upvote posts that help you. $\endgroup$ – Raphael Dec 18 '15 at 6:34
  • $\begingroup$ Hi @Raphael I did upvote your answer but it appears I need 15 reputations for my vote to be publicly displayed. $\endgroup$ – Huy Anh Nguyễn Dec 18 '15 at 23:33

how we can preserve the information across multiple calls.

Excactly; we use a standard trick of functional programming and add additional parameters to the recursion.

Idea: Store (a copy of the) call stack in an array. Then, all ancestors of the current node are accessible in $O(1)$ time. You can do BFS or DFS.

Details: The main procedure starts at the root and creates an empty array of sufficient size:

relabel(T : Tree) {
  relabelH(T, 0, new Tree[T.size])

The second parameter stands for the current index in the array (i.e. recursion depth) which we use to determine the index of the $k$th ancestor. The actual work is done here:

relabelH(T : Tree, level : Int, ancestors : Tree[]) {
  ancestors[level] = T
  T.label = ancestors[max(0, level - T.label)].label

  for c in T.children {
    relabelH(c, level + 1, ancestors)

Correctness: You can show by induction that ancestors[0..level-1] always contains the current node's ancestors in order from root to parent. Hence, the label update is correct. All nodes are reached (we do DFS) so the procedure is correct.

Running time: Every line in relabelH is executed once per visited node. Every individual line runs in constant time, assuming a reasonable implementation of Tree. The main call relabel(T) takes linear time (array initialization) plus the cost of the call to relabelH. In total, we get a running time in $\Theta(n)$ with $n$ the number of nodes (T.size).

  • $\begingroup$ Of course, once you have made the node history explicit, you no longer need recursion. I kept it for clarity; real implementation would use a loop for efficiency. $\endgroup$ – Raphael Dec 15 '15 at 10:40

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.