sum of leaves in binary tree
Jul 10, 2012 at 9:24am UTC
hi
i'm trying to write a c code that calculates the sum of the leaves(only leaves) in a binary tree using recursion but its no worked out to me
please help me if you can
1 2 3 4 5 6 7 8 9 10 11 12
int sumOfLeaves(Tree* root){
int sum=0;
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return sum+=root->key;
if (root->left != NULL)
return (sumOfLeaves(root->left);
if (root->right!= NULL)
return (sumOfLeaves(root->right);
return sum;
}
i wrote this but its return me 5
the tree looks like:
8
/ \
2 10
\ / \
6 9 16
/
5
its need to return - sum = 5+9+16 = 30
thanks
Last edited on Jul 10, 2012 at 12:30pm UTC
Jul 10, 2012 at 11:03am UTC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
int sumOfLeaves(Tree* root)
{
int sum = 0;
if (!root)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return sum += root->key;
}
if (root->left != NULL)
{
return (sumOfLeaves(root->left);
}
if (root->right != NULL)
{
return (sumOfLeaves(root->right);
}
return sum;
}
Can you post the Tree structure here ?
I wanna know what
root->key is
And was
8 the input for the example tree?
Jul 10, 2012 at 11:13am UTC
the tree structure is:
1 2 3 4 5
typedef struct Tree{
int key;
struct Tree* left;
struct Tree* right;
}Tree;
root is variable of type Tree*
and the tree in my first post is the tree i want to sum it leaves
thank you!
Last edited on Jul 10, 2012 at 12:31pm UTC
Jul 10, 2012 at 11:17am UTC
1 2 3 4 5 6 7 8 9 10 11
if (root->left != NULL)
{
return (sumOfLeaves(root->left);
}
if (root->right != NULL)
{
return (sumOfLeaves(root->right);
}
return sum;
can be replaced with simply
return sumOfLeaves(root->left) + sumOfLeaves(root->right)
Jul 10, 2012 at 11:27am UTC
ok i replaced that and it still not work well..
Jul 10, 2012 at 11:36am UTC
What are you getting then?
You should also replace
1 2 3 4
if (root->left == NULL && root->right == NULL)
{
return sum += root->key;
}
with
1 2 3 4
if (root->left == NULL && root->right == NULL)
{
return root->key;
}
And see if that works
Last edited on Jul 10, 2012 at 11:36am UTC
Jul 10, 2012 at 11:44am UTC
1 2 3 4 5 6 7 8 9 10 11
if (root->left != NULL)
{
return (sumOfLeaves(root->left);
}
if (root->right != NULL)
{
return (sumOfLeaves(root->right);
}
return sum;
The problem lies here.
When the program get to the test for
root->left , initially
left will not be
NULL , so it will call the
sumOfLeaves() .
It gets into
sumOfLeaves() once again, and repeat the same process when it get to
root->left test.
Eventually
root->left will be NULL as the last leaves in the tree is reached, the program now then
which in this case is
5 .
one more important thing is that
1 2 3 4 5
int sumOfLeaves(Tree* root)
{
int sum = 0;
//so on
}
by doing this, you will reset sum back to 0 every time this function is called which means you will never get the sum you need
Last edited on Jul 10, 2012 at 11:46am UTC
Jul 10, 2012 at 11:49am UTC
it throws me from the program when i run it
i cant find the problem :(
Jul 10, 2012 at 11:52am UTC
You mean it just closes?
The problem shouldn't be in this function, so we'll need to see more code (dont forget the code tags, the <> icon to the right).
Jul 10, 2012 at 11:55am UTC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
int sum = 0;
int sumOfLeaves(Tree* root)
{
if (!root)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
sum += root->key;
}
if (root->left != NULL)
{
sum += sumOfLeaves(root->left);
}
if (root->right != NULL)
{
sum += sumOfLeaves(root->right);
}
return sum;
}
Can you try with this piece of code?
Jul 10, 2012 at 11:58am UTC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
typedef struct Tree
{
int key;
struct Tree* left;
struct Tree* right;
}Tree;
int sumOfLeaves(Tree* root)
{
if (root->left == NULL && root->right ==NULL)
return root->key;
return sumOfLeaves(root->left) + sumOfLeaves(root->right)
}
int main
{
Tree* t = createTree(8); //function to create tree
addToTree(10,t);
addToTree(16,t); //adding numbers to the nodes of tree
addToTree(2,t);
addToTree(6,t);
addToTree(9,t);
addToTree(5,t);
printf("Sum: %d" ,sumOfLeaves(t)); //this should print the sum of leaves
return 0;
it's looks fine but when i run it its just give me a runtime error and close
i tried to debug it but i cant find the problem.
Last edited on Jul 10, 2012 at 12:06pm UTC
Jul 10, 2012 at 12:07pm UTC
What does the addToTree function look like?
EDIT:
Also, I noticed you removed
1 2 3 4
if (!root)
{
return 0;
}
You should put that back in, because with it there are only two states that really matter, both children for a root is null, or they're not (which means both or one is not null). If they're both null you just return the value of the root, if they're not you call sumOfLeaves recursively, and if one of the children happens to be null you just return a 0.
Last edited on Jul 10, 2012 at 12:13pm UTC
Jul 10, 2012 at 12:18pm UTC
all the other functions works fine ..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Tree* addToTree(int key,Tree* root)
{
if (!root)
{
Tree* t = createTree(key);
return t;
}
if (key > root->key)
root->right = addToTree(key,root->right);
else if (key < root->key)
root->left = addToTree(key,root->left);
else
{
//value is exist we dont add it
}
return root;
}
Jul 10, 2012 at 12:22pm UTC
Its working!!!!!!!!!!!!
i add back the if(!root)
and its working well!
thank you !!
Jul 10, 2012 at 12:23pm UTC
The final function that works looks like :
1 2 3 4 5 6 7
int sumOfLeaves(Tree* root){
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return root->key;
return sumOfLeaves(root->left) + sumOfLeaves(root->right);
}
Topic archived. No new replies allowed.