Binary Search Tree Finding Odd values problem

Binary Search Tree Finding Odd values problem

Page 1 of 1

7 Replies - 2447 Views - Last Post: 15 October 2010 - 02:00 PM Rate Topic: ***** 1 Votes

#1 chintan_1671  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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.

Please help me out.

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree Finding Odd values problem

#2 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#3 chintan_1671  Icon User is offline

  • New D.I.C Head

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

Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 12:52 PM

View PostOler1s, 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.
Please elaborate.

Thanks
Was This Post Helpful? 0
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 336
  • View blog
  • Posts: 727
  • Joined: 27-June 09

Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:02 PM

View Postchintan_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.
Was This Post Helpful? 0
  • +
  • -

#5 chintan_1671  Icon User is offline

  • New D.I.C Head

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

Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 01:22 PM

View Postmojo666, on 15 October 2010 - 12:02 PM, said:

View Postchintan_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.



Thanks for your reply.
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
Was This Post Helpful? 0
  • +
  • -

#6 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • 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?
What about getLeafCount(node->right, temp)?
Was This Post Helpful? 0
  • +
  • -

#7 chintan_1671  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#8 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 336
  • View blog
  • Posts: 727
  • Joined: 27-June 09

Re: Binary Search Tree Finding Odd values problem

Posted 15 October 2010 - 02:00 PM

View Postchintan_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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1