sum of leaves in binary tree

Jul 10, 2012 at 9:24am
yyoni69 (27)
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
Jul 10, 2012 at 11:03am
ThangDo (124)
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
yyoni69 (27)
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
Jul 10, 2012 at 11:17am
Warnis (230)
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
yyoni69 (27)
ok i replaced that and it still not work well..
Jul 10, 2012 at 11:36am
Warnis (230)
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
Jul 10, 2012 at 11:44am
ThangDo (124)
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
return sum += root->key;
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
Jul 10, 2012 at 11:49am
yyoni69 (27)
it throws me from the program when i run it
i cant find the problem :(
Jul 10, 2012 at 11:52am
Warnis (230)
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
ThangDo (124)
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
yyoni69 (27)
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
Jul 10, 2012 at 12:07pm
Warnis (230)
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
Jul 10, 2012 at 12:18pm
yyoni69 (27)
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
yyoni69 (27)
Its working!!!!!!!!!!!!
i add back the if(!root)
and its working well!

thank you !!
Jul 10, 2012 at 12:23pm
yyoni69 (27)
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.