C++

Forum

 
sum of leaves in binary tree

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
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?
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
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)
yyoni69 (27)
ok i replaced that and it still not work well..
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
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
yyoni69 (27)
it throws me from the program when i run it
i cant find the problem :(
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).
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?
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
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
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;
}
yyoni69 (27)
Its working!!!!!!!!!!!!
i add back the if(!root)
and its working well!

thank you !!
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.