$($a$)$ Describe your algorithm clearly in English.

$($b$)$ Give pseudocode.

$($c$)$ Argue correctness, even if you don$$t give a formal proof and give a convincing

argument instead.

$($d$)$ Give with explanation the best upper bound that you can for the running time. Question: Trees can be used to represent hierarchical relationships. For example, a tree

could represent reporting relationships in a company, e$.$g$.,$ engineers report to their team

manager who reports to a more senior manager, who reports to a director, etc.

Suppose you are given a binary tree T $=($V$,$ E$)$ with root r representing a hierarchical

relationship.

$($a$)$ You expect to receive several queries of the form $$Is u an ancestor of v in

T$?$ You wish to answer each such query in constant time. To this end, you decide to

spend linear time to preprocess the tree so you can answer any query of the above form

in constant time.

Describe the preprocessing you will do$,$ and how it will allow you to answer a query in

O$(1)$ time.

$($b$)$ You are now given an array s with a value for each node in V $.$ Define a new

array $$ such that

$[$u$]=$ the maximum of the s$-$values associated with u$$s descendants.

Give a linear$-$time algorithm to fill in the array $.$