Question

8. You are given a binary tree T (V,E) with a designated root node. In addition, there is an array z with a value for each node in V. Define a new array z as follows: for each u e V, zu is the maximum of the -values associated with u's descendants. Give a linear-time algorithm which calculates the entire z array. (7 points)

Answer 1

When we represent the values of nodes of the binary tree T in the form of an array.

We know that, any node present at the position 'i' in the index has :

Left child at position = 2i+1 and

Right child at position = 2i+2

Therefore, for every i in the array, we just need to get the maximum of the value present at '2i+1' and '2i+2'.

This will get you the answer in linear time.

ALGORITHM:

for i = 0:sizeof(x)

if( 2i+2 <= sizeof(x) )

temp = max( x[2i+1] , x[2i+2] )

else

temp = -1

z[i] = temp

return z