Question

Design a recursive algorithm with proofs of the following:

Richest Heritage:

Input: A binary tree T in which each node x contains a field worth[x], which is a (positive, zero, or negative) monetary value expressed as a real number.

Define (monetary) heritageof a node x to be the total worth of ancestors of x minus the total worth of proper descendants of x.

Output: A node x in T with maximum heritage

Note: other than the field worthand left/right child pointers, nodes of the given tree do not have any additional fields that you may use to store computed values. You are not allowed to alter the content of any nodeor create a “working copy” of the tree.]

Answer 1