Question

You are given tree T=(V,E) along with a designated root node $\mathit{r}\mathbf{\in }\mathit{V}$. The parent of any node $\mathit{V}\mathbf{\ne }\mathit{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 ${\mathit{p}}^{\mathbf{k}}\left(v\right){\mathit{p}}^{\mathbf{k}\mathbf{-}\mathbf{1}}\left(p\left(v\right)\right)\mathbf{}\mathbf{and}\mathbf{}{\mathbf{p}}^{\mathbf{1}}\left(v\right)\mathbf{=}\mathbf{p}\left(v\right)$(so ${\mathit{p}}^{\mathbf{k}}\left(v\right)$is the k th ancestor of v ). Each vertex v of the tree has an associated non-negative integer label l(v). Given a linear-time algorithm to update the labels of all the vertices T according to the following rule: ${\mathit{l}}_{\mathbf{n}\mathbf{e}\mathbf{w}}\left(v\right)\mathbf{=}\mathit{l}\left(p^{l\left(v\right)}\left(v\right)\right)$.

Short answer

Depth-first search algorithm can be used to update the labels of all vertices T according to the rule $l_{new}\left(v\right)=l\left(p^{l\left(v\right)}\left(v\right)\right)$.

Step-by-step solution

Explain Depth-first search

Depth-first search is the linear time algorithm that gives information about a graph. A graph is considered in the form of an adjacency list. Neighbors of the vertices can be found by exploring the vertices and marking the visited vertices.

Give a linear-time algorithm to update the labels of all the vertices T  

Consider the binary tree T =(v,E) with the designated root node $r\in V$. The parent of any node $v\ne r$, denoted p (v), is the node adjacent to v in the path from r to v . By convention p (r)=r .

For k>1 ,define $p^k\left(v\right)=p^{k-1}\left(p\left(v\right)\right)$and $p^1\left(v\right)=p\left(v\right)$. Each vertex v of the tree has an associated non-negative integer label $l\left(v\right)$.

Consider the following algorithm,that updates the labels of all vertices $T$according to the rule $l_{new}\left(v\right)=l\left(p^{l\left(v\right)}\left(v\right)\right)$.

Input: $T\left(V,E\right)$

Output: $I_{new}\left(v\right)$

Procedure:

perform DFS on$T\left(V,E\right)$

Declare DFS on stack

During traversal

if node v is pushed onto the stack

update $I_{new}\left(v\right)=1\left(stack.at\left(max\left(stack,size\left(\right)-1\left(v\right),1\right)\right)\right)$

at $stack.at\left(I\right)$

take out the vertex at ith position

set bottom element to be in the first position

return $I_{new}\left(v\right)$

The above algorithm considers the stack to perform DFS. During traversal if node is pushed onto the stack, then the label of the vertex at stack is updated. Then the vertex is moved to the bottom and the bottom element is moved to the first position.

Therefore, Depth-first search algorithm has been used to update the labels of all vertices T according to the rule $I_{new}\left(v\right)=I\left(p^{I\left(v\right)}\left(v\right)\right).$