Write a recursive function sumTreeNodeHelper(struct BNode *node, double *sum) th

Question

Write a recursive function sumTreeNodeHelper(struct BNode *node, double *sum) that sums the elements of a binary search tree starting with the smallest element, and adding elements in order up to the largest element and prints the running sum as each new value (i.e., node->val) is added to the sum (We assume double values are stored in the tree). You will not use an iterator.

void sumTreeNodeHelper(struct BNode *node, double *sum)

{ printf(“Running sum = %f ”, *sum);

}

void sumTree(struct BSTree *tree, double *sum)

{ sumTreeNodeHelper(tree->root, sum);

}

/* Example use */

struct BSTree myTree; int sum = 0;

/* Initialize and Add elements to the tree */

addTree(&myTree, 5);

addTree(&myTree, 1);

addTree(&myTree 10);

sumTree(&myTree, &sum);

printf(“Final sum = %f ”, sum); …

The output of the above should be:

Running sum = 1

Running sum = 6

Running sum = 16

Final sum = 16

Explanation / Answer

I have used inorder traversal to visit nodes in increasing order.

C code:

#include<stdio.h>
#include<stdlib.h>
  
struct mynode
{
double key;
struct mynode *left, *right;
};
  

struct mynode *newNode(double item)
{
struct mynode *temp = (struct mynode *)malloc(sizeof(struct mynode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
  
void sumTreeNodeHelper(struct mynode *root, double *ptr)
{
if (root != NULL)
{
sumTreeNodeHelper(root->left,ptr);
printf("Current sum = %f ", ((root->key) + *ptr) );
*ptr = *ptr + (root->key);
sumTreeNodeHelper(root->right, ptr);
}
}
  
struct mynode* addTree(struct mynode* mynode, double key)
{

if (mynode == NULL)
{
return newNode(key);
}
if (key < mynode->key)
{
mynode->left = addTree(mynode->left, key);
}
else if (key > mynode->key)
{
mynode->right = addTree(mynode->right, key);   
}
return mynode;
}
  
int main()
{
struct mynode *root = NULL;
root = addTree(root, 5);
addTree(root, 1);
addTree(root, 10);
double sum = 0;
double *ptr = &sum;
//Use sumTreeNodeHelper traversal to visit mynodes in increasing order
sumTreeNodeHelper(root, ptr);
printf("Final sum = %f ",*ptr );
return 0;
}

Sample Output:

Current sum = 1.000000
Current sum = 6.000000
Current sum = 16.000000
Final sum = 16.000000

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.