Question

. [25 pts.] Tree node with largest value children. Consider a complete ternary tree where each node apart from the leaves has exactly 3 children and is associated with a numeric key k.

a [15 pts.] Write the pseudo-code of a procedure that returns the node whose children have the largest sum of keys, i.e. the score of a node is the sum of its children key values. Note that leaves would not be considered as they do not have children.

b [10 pts.] What is the asymptotic running time O() of the algorithm for a tree of n nodes? Show your derivation.

Answer 1

Do like and comment if you have any queries.

Answer: