Tree Traversal

Question

Let $T(V, E)$ be a weighted tree rooted at node $r ∈ V$. We define $M(r, v)$ to be the weight of the largest weighted edge on the path from $r$ to $v$. The following figure shows an example.

$M(r, a) = 5, M(r, b) = 9, M(r, c) = 5, M(r, d) = 5, M(r, e) = 11, M(r, f) = -3, M(r, g) = -3$

$M(r, h) = 9,M(r, i) = 8, M(r, j) = 10, M(r, k) = 8, M(r, l) = 7$.

Please design an O(n) algorithm to compute $M(r, v)$ for each and every node $v (≠ r)$ in $V$. We assume, for each node $u$, its father $π(u)$ is known $(π(r) = r)$, and its children are organized by a linked list. You can simply call “u’s next son” to get its next son or first son. “u’s next son = $nil$” means you have looked all its sons or it is a leaf.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
M(r,r) = - ∞ 
π(r) = r

for each r’s next son:
    Tree-Traversal( T, r, r.next )

Tree-Traversal(T,r,v)
    if v = nil :
        return nil
    else :
        M(r,v) ← MAX ( w(π(v),v) ,M(r,π(v)))
        for each v’s next son:
            Tree-Traversal( T, r, v.next )
End

The Time Complexity is $O(n)$, since we visite all the node of tree once. alternative solution: We remove the root's loop and assume that $w(r,r) = - ∞$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
M(r,r) = - ∞ 
w(r,r) = - ∞
π(r) = r
v = r           # start traversal from the root r
Tree-Traversal(T,r,v)
    if v = nil :
        return nil
    else :
        M(r,v) ← MAX ( w(π(v),v) ,M(r,π(v)))
        For each v’s next son:
            Tree-Traversal( T, r, v.next )
End