Question

You are given a tree T = (V;E) along with a designated root node r 2 V . The parent of any node v 6= r , denoted p(v), is de ned to be the node adjacent to v in the path from r to v. By convention, p(r) = r. For k > 1, de ne pk(v) = pk????1(p(v)) and p1(v) = p(v) (so pk(v) is the kth 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 rule lnew(v) = l(pl(v)(v)).

Answer 1

Solution and Explanation:

Linear time algorithm to update the label of all vertices in T :

-> It is given that the binary tree " T = ( V , E ) " with root node " r E V " . " P( V ) " is the node adjacent to ' V ' in the path from " r " to " V ".

-> By rule , "P ( r ) = r " and is defined that "Pk ( V ) - P k-1 ( P (V )) " and " P " (V ) = P (V )' for "K > 1 "

-> From the above defined statement , it means that

Pt ( V )" is ancestor of " V "

-> In this binary tree, each vertex , " V " is associated with the non - negative integer label "l(V)"

The following linear time alogrithm maintains the label of all the vertices currently on stack in an individually array. As the path may contain at 'n' vertices in tree, so the length of array is at most 'n'.

Please see the attached file.