# Binary Search Tree Finding Odd values problem

Page 1 of 1

## 7 Replies - 9716 Views - Last Post: 15 October 2010 - 02:00 PMRate Topic: 1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=195159&amp;s=127541954a9b81917e400ce030b1bf8e&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 chintan_1671

Reputation: 2
• Posts: 46
• Joined: 22-December 08

# Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 11:58 AM

I have created a binary tree. I have a function which counts the odd values from nodes of tree.
I am always getting the output as if it is just returning the odd count from node->right.

I am loosing the value of node->left count.

```#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

struct node
{
int data;
struct node* left;
struct node* right;
};

int getLeafCount(struct node* node, int count)
{

int temp = 0;
if(node!=NULL)
{
if((node -> data %2) != 0)
{
temp++;
count = count + temp;
}
getLeafCount(node->left, count);
getLeafCount(node->right, count);
}
return count;
}

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

int main()
{
struct node *root = newNode(1);
root->left        = newNode(2);
root->right       = newNode(3);
root->left->left  = newNode(4);
root->left->right = newNode(5);

int tot_cnt = getLeafCount(root, 0);
cout << "Total Count: " << tot_cnt;

getchar();
return 0;
}

```

I am always gettin o/p as 1 instead if 3.

Thanks

Is This A Good Question/Topic? 0

## Replies To: Binary Search Tree Finding Odd values problem

### #2 Oler1s

• D.I.C Lover

Reputation: 1397
• Posts: 3,884
• Joined: 04-June 09

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 12:43 PM

Are you aware that in passing function arguments, a copy is made?

### #3 chintan_1671

Reputation: 2
• Posts: 46
• Joined: 22-December 08

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 12:52 PM

Oler1s, on 15 October 2010 - 11:43 AM, said:

Are you aware that in passing function arguments, a copy is made?

Not sure what does that mean.

Thanks

### #4 mojo666

Reputation: 408
• Posts: 882
• Joined: 27-June 09

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:02 PM

chintan_1671, on 15 October 2010 - 10:58 AM, said:

```int getLeafCount(struct node* node, int count)
{

int temp = 0;
if(node!=NULL)
{
if((node -> data %2) != 0)
{
temp++;
count = count + temp;
}
getLeafCount(node->left, count);
getLeafCount(node->right, count);
}
return count;
}
```

count is not a global variable. It does not retain its value when you make a recursive call. I suppose this could be remedied by passing by reference, but there is a more elegant solution.

You need to take advantage of the fact that greenLeafCount returns the number of odd numbers in the tree rooted at the node argument. As written, your code does nothing with the results of the recursive calls. You should be aiming for something like
```temp = getLeafCount(node->left, count) + getLeafCount(node->right, count);

```

temp now contains the total number of odd numbers below the current node. Add 1 if the current node is odd, and return the result.

### #5 chintan_1671

Reputation: 2
• Posts: 46
• Joined: 22-December 08

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:22 PM

mojo666, on 15 October 2010 - 12:02 PM, said:

chintan_1671, on 15 October 2010 - 10:58 AM, said:

```int getLeafCount(struct node* node, int count)
{

int temp = 0;
if(node!=NULL)
{
if((node -> data %2) != 0)
{
temp++;
count = count + temp;
}
getLeafCount(node->left, count);
getLeafCount(node->right, count);
}
return count;
}
```

count is not a global variable. It does not retain its value when you make a recursive call. I suppose this could be remedied by passing by reference, but there is a more elegant solution.

You need to take advantage of the fact that greenLeafCount returns the number of odd numbers in the tree rooted at the node argument. As written, your code does nothing with the results of the recursive calls. You should be aiming for something like
```temp = getLeafCount(node->left, count) + getLeafCount(node->right, count);

```

temp now contains the total number of odd numbers below the current node. Add 1 if the current node is odd, and return the result.

I have changed the code to:
```int getLeafCount(struct node* node, int count)
{
int temp = 0;

if(node!=NULL)
{
if((node -> data %2) != 0)
{
temp++;
count = count + temp;
}
count = getLeafCount(node->left, temp) + getLeafCount(node->right, temp);
}
return count;
}

```

it is giving me proper output for all input except if there is only 1 node.
It gives me output as count:2 if there is only 1 node which is odd.

Please let me know where am i going wrong.

Thanks

### #6 Oler1s

• D.I.C Lover

Reputation: 1397
• Posts: 3,884
• Joined: 04-June 09

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:39 PM

```count = getLeafCount(node->left, temp) + getLeafCount(node->right, temp);
```

If there's only one node, with odd data, how does the expression evaluate? What does getLeafCount(node->left, temp) get you? 0? 2? 5? 10?

### #7 chintan_1671

Reputation: 2
• Posts: 46
• Joined: 22-December 08

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:44 PM

I have solved my problem.
Thanks for the helps.

```int getLeafCount(struct node* node, int count)
{
int temp = 0;

if(node!=NULL)
{
count = getLeafCount(node->left, temp) + getLeafCount(node->right, temp);
if((node -> data %2) != 0)
count ++;
}
return count;
}

```

I have to solve this also with iterative menthod.
Could any one please give me any idea how it can be solved.
Any algorithm or idea would be really appreciated.

Thanks

This post has been edited by chintan_1671: 15 October 2010 - 01:52 PM

### #8 mojo666

Reputation: 408
• Posts: 882
• Joined: 27-June 09

## Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 02:00 PM

chintan_1671, on 15 October 2010 - 12:44 PM, said:

```int getLeafCount(struct node* node, int count)
{
int temp = 0;

if(node!=NULL)
{
count = getLeafCount(node->left, temp) + getLeafCount(node->right, temp);
if((node -> data %2) != 0)
count ++;
}
return count;
}

```

Not bad, but may I suggest this cleaner version
```int getLeafCount(struct node* node)
{
int count = 0;

if(node!=NULL)
{
count = getLeafCount(node->left) + getLeafCount(node->right);
if((node -> data %2) != 0)
count ++;
}
return count;
}

```

This eliminates any confusion about the variables. No variable besides node needs to be passed. In your code, temp is never anything but 0. It is not even used except to "initialize" count in the recursive call. Rather than pass 0 this way, just initialize count at the begining.

As for iterative methods, try looking up depth-first and breadth-first traversal algorithms.