Find the sum of data stored in all non leaf of Binary Search Tree? (a standalone recursive function that returns an integer.)
Find the sum of data stored in all non leaf of Binary Search Tree? (a standalone recursive function that returns an integer.)
So, the is the problem statement where I am stuck and trying to seek help for it is the following:
As a part of my assignment, we have been asked to find the sum of the data stored in all the leaf nodes of BST. We have been the function's template:
friend int Sum_Node_leaf_Data(BST *Root)
And below is the memory of an object of the following class acts as the node of a linked list representing Binary Search Tree of integers.
If any one can suggest a different logic for it.
I am unable to fix my logical error if any of you can point out and suggest something, would be a great help.
class BST
private: int info;
BST *left;
BST *right;
public: BST () //NULL Constructor.
;
the logic that I formed for this problem is that, I declare and initial an integer type variable 'sum' to zero. ii) checked whether the root address points to Null. If it does not, iii) checked whether both 'left' and 'right' pointers point to Null, if false, then sum is added by the 'info' stored at where root pointer points.Once its added, iv) two recursive calls to the same function are made passing 'root->left' and 'root_>right' respectively.
int Sum_Non_Leaf_Data(BST *Root)
int sum =0;
if(Root != NULL)
if(Root->left != NULL && Root->right !=NULL)
sum += Root_info;
Sum_Node_Leaf_Data(Root->left);
Sum_Node_Leaf_Data(Root->right);
return sum;
But the problem is, since it's a recurive function the value of sum is getting reinitialized every time so how can I return the integer value of the 'sum'.
return sum;
I added that but since the value of sum is getting re-initialed on every call it is not return the correct sum of all non leaf nodes in BST.
– Devanshi Sukhija
Sep 16 '18 at 13:16
You must not ignore the return value of the recursive call
Sum_Node_Leaf_Data(Root->left);.– melpomene
Sep 16 '18 at 13:17
Sum_Node_Leaf_Data(Root->left);
Is "
friend in" valid C++ syntax?– Thomas Matthews
Sep 16 '18 at 17:34
friend in
"the value of sum is getting reinitialized every time" No, there are distinct values named
sum for each call of this function– Caleth
Sep 17 '18 at 9:29
sum
3 Answers
3
I believe this code is much cleaner than the accepted answer:
int internal_node_sum(BST *node)
Note that due to short-circuiting, a null pointer won't be dereferenced in the if condition in the case of an empty list.
if
you should not ignore the return values of your recursive function. The code below should solve your problem:
int Sum_Non_Leaf_Data(BST *Root)
int sum =0;
if(Root != NULL)
if(Root->left != NULL && Root->right !=NULL)
sum += Root->info;
sum+=Sum_Node_Leaf_Data(Root->left);
sum+=Sum_Node_Leaf_Data(Root->right);
return sum;
Your code has multiple syntax errors. It's also a bit odd to call the function parameter
root when it's a recursive function.– Mike Borkland
Sep 16 '18 at 13:53
root
Also, an execution path in your function allows it to reach the end without returning a value. Going to downvote because of this.
– Mike Borkland
Sep 16 '18 at 13:57
@Mike Borkland: The reason behind posting the code is to highlight the add operation and is nothing related to what variable name you use for representation
– Maddy
Sep 16 '18 at 14:29
First lets address a misconception that you have
since it's a recurive function the value of sum is getting reinitialized every time
No, there are distinct values named sum for each call of this function. You can add the result from the children to your sum accumulator (As Mike's answer demonstrates).
But you don't even need a sum in this function
sum
int internal_node_sum(BST * node)
if (node && node->left && node->right)
return node->info
+ internal_node_sum(node->left)
+ internal_node_sum(node->right);
return 0;
Thanks for contributing an answer to Stack Overflow!
But avoid …
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy
"how can I return the integer value of the 'sum'" -
return sum;?– melpomene
Sep 16 '18 at 13:13