Question

As in the previous problem, you are given a binary tree T=(V,E) with designated root node. In addition, there is an array $\mathit{x}[.]$with a value for each node in V Define a new array $\mathit{z}\mathbf{[}\mathbf{.}\mathbf{]}$as follows: for each $\mathit{u}\mathbf{\in }\mathit{V}$,

$\mathit{z}\mathbf{\left[}\mathbf{u}\mathbf{\right]}\mathbf{=}$the maximum of the x-values associated with u’s descendants.

Give a linear-time algorithm that calculates the entire z-array.

Short answer

A linear-time algorithm is as follows.

Input: BinaryTree T=(v,E)

Output: z[.] for each $u\in V$

Initialize z{i} to 0,

Begin procedure DFS ( )

While traversal

if node pops out of the stack

update the z values of the node u at the top of the stack

z{u} =max (z{u},x{v})

return z{u}

Step-by-step solution

Explain Binary tree

Consider the binary tree T=(V,E) with the root node. A binary tree must have at most two children for every parent node.

Give a linear-time algorithm that calculates the entire z -array.

Consider the binary tree T=(V,E)with the designated root node. Array x{.} with a value for each each node in V is given.

Create new array z{.} for each $u\in V$,

z{u}= the maximum of the x -values associated with u’s descendants.

Considering the given information, a linear-time algorithm is as follows.

Input: BinaryTree T=(V,E)

Output: z{.} for each $u\in V$

Initialize z{i} to 0,

Begin procedure DFS()

While traversal

if node pops out of the stack

update the z value of the node u at the top of the stack

z{u}=max(z{u},x{v}

return z{u}

The above algorithm initializes the z array, and performs the depth first search. During traversal , if the node pops out of the stack , update the z value of the node u. This algorithm runs in linear time.

Therefore, a linear-time algorithm that calculates the entire z-array has been provided.