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

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 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 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 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] 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 15 minutes ago

asked 21 minutes ago

asked 30 minutes ago

asked 37 minutes ago

asked 37 minutes ago

asked 46 minutes ago

asked 46 minutes ago

asked 46 minutes ago

asked 51 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago