Write a recursive function sumTreeNodeHelper that sums the elements of a binary

Question

Write a recursive function sumTreeNodeHelper 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 (ie. Node->val) is added to the sum (We’re assuming 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 of tree values = %f ”, sum);
…< /span>

The output of the above should be:

Running sum = 1
Running sum = 6
Running sum = 16
Final sum of tree values = 16

Explanation / Answer

//Please see the below answer

#include<iostream>
using namespace std;

struct BSTree
{
     int val;
     struct BSTree* left;
     struct BSTree* right;
};
struct BSTree myTree;

struct BSTree* newNode(int value)
{
     struct BSTree* node = (struct BSTree*)malloc(sizeof(struct BSTree));
     node->val = value;
     node->left = NULL;
     node->right = NULL;
     return(node);
}

struct BSTree* addTree(struct BSTree* node, int value)
{
    if (node == NULL)
       return newNode(value);
   
    if (value < node->val)
        node->left = addTree(node->left, value);
    else if (value > node->val)
        node->right = addTree(node->right, value);
     return node;
}

void sumTreeNodeHelper(struct BSTree *node, int *sum)
{

    if (node != NULL)
    {
        sumTreeNodeHelper(node->left,sum);
       *sum=*sum+node->val;
        printf("Running sum = %d ", *sum);
        sumTreeNodeHelper(node->right,sum);
    }

}

/*
void sumTree(struct BSTree *tree, double *sum)
{
   sumTreeNodeHelper(&myTree, &sum);

}*/


int main()
{
  
   int sum = 0;
   /* Initialize and Add elements to the tree */
   addTree(&myTree, 5);
   addTree(&myTree, 1);
   addTree(&myTree, 10);
  

   sumTreeNodeHelper(&myTree, &sum);
   printf("Final sum of tree values = %d ", sum);
   return 0;
}

OUTPUT:

Running sum = 1

Running sum = 6
Running sum = 16

Final sum of tree values = 16

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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