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

Answer 1

/*Function to print the maximum monetory value in a tree*/
printMaxval(tree)
maxval=0;
for d = 1 to height(tree)
   if(maxval<MaxMonetory(tree, d, maxval))
   maxval=MaxMonetory(tree, d, maxval);
print maxval;

Maxmonetory(tree, level, maxval)
if tree is NULL then return 0;
if level is 1, and monetorydata>maxval then
maxval=monetorydata;
return maxval;
else if level greater than 1, then
    Maxmonetory(tree->left, level-1, maxval);
    Maxmonetory(tree->right, level-1, maxval);