Question

Design a recursive algorithm with proofs of the following: Richest Heritage: Input: A binary tree T...

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

Homework Answers

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);

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Design a recursive algorithm with proofs of the following: Richest Heritage: Input: A binary tree T...
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...
Input: A binary tree T in which each node x contains a field worth[x], which is...
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) heritage of 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 worth and left/right child pointers, nodes of the given tree do not have...
a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search...
a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search tree. Describe your algorithm in English or with a simple pseudocode program. b) (3 bonus pts.) Extend the algorithm in a) to test whether a binary tree is an AVL tree.
Design a recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns...
Design a recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns the total number of 1’s in n’s binary representation. Note that the input is n, not its binary representation. For example, A(9) should return 2 as 9’s binary representation is 1001, while A(7) should return 3 since 7 is 111 in binary. Note that your algorithm should have a running time of O(log n). Justify your answer. You need to do the following: (1)...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT
Active Questions
  • For all of the following experiments, under standard conditions, which species could be spontaneously produced? Oxygen...
    asked 15 minutes ago
  • The article “Gas Cooking, Kitchen Ventilation, and Exposure to Combustion Products” reported that for a sample...
    asked 21 minutes ago
  • 1)“Joe has a dog” is a sufficient condition for (select one) a. "Joe has an animal”...
    asked 30 minutes ago
  • The director of research and development is testing a new medicine. She wants to know if...
    asked 37 minutes ago
  • Question 3. Every 2 years, the National Assessment of Educational Progress (NAEP) assesses nationally representative samples...
    asked 37 minutes ago
  • The assets of four wealthiest people in a particular country are 29, 27, 14, 10. Assume...
    asked 46 minutes ago
  • Describe one personality trait that you believe to be highly heritable (mostly a product of genetics)...
    asked 46 minutes ago
  • In this problem your task is to find a missing number. The input will always consist...
    asked 46 minutes ago
  • In a study of the accuracy of fast food​ drive-through orders, Restaurant A had 245245 accurate...
    asked 51 minutes ago
  • Write a set of two-sample t-test hypotheses using symbols for each of the following situations. Define...
    asked 1 hour ago
  • Address each of the Three C's ( Content, Contect, Consequences) and determine if the individual would...
    asked 1 hour ago
  • Here are summary statistics for randomly selected weights of newborn​ girls: n=168​, x =28.7 ​hg, s=6.1...
    asked 1 hour ago