Programming Forums > Application Development > C++

BaroN NighT · Apr 26th, 2005, 9:48 PM

I'm trying to write a function that counts the total number of leaf nodes in a binary search tree:

int tree::sumLeaf(node* node1) {
  int sumnodes = 0;
  
  if(node1==NULL){
   return (0);                
  }
  sumnodes=sumLeaf(node1->left);
  if(node1!=NULL && node1->left==NULL && node1->right==NULL){
   return sumnodes++;
  }

You can see that I'm trying to figure out to count it by going through all the way to the left first. Considering a binary search tree with the order of insertion: 15,7,85,10,2,99,66,50,43,15...the function should print 1 (for the leaf node containing the number 2). But it prints 0. Any help would be highly appreciated

.

uman · Apr 26th, 2005, 9:51 PM

(Toggle Plain Text)

//UNTESTED!
int tree::sumLeaf(node* node1)
{       
        if(node1 == NULL) return 0;
        return sumLeaf(node1->left) + sumLeaf(node1->right) + 1;
}

BaroN NighT · Apr 26th, 2005, 9:56 PM

Thank you for your prompt reply uman, but this function counts the total number of all the nodes, not the number of leaf nodes.

uman · Apr 26th, 2005, 10:03 PM

whoops :-P. Sorry. Let me finish cleaning my room and I'll see what I can do.

BaroN NighT · Apr 26th, 2005, 10:12 PM

I don't even know if this is right(now I'm trying to count all the leaf nodes,right and left, not like the first one above):

(Toggle Plain Text)

int tree::sumLeaf(node* node1) {
  int sumnodes = 0;
  
  if(node1==NULL){
   return (0);                
  }
  sumnodes=sumLeaf(node1->left);
  sumnodes=sumLeaf(node1->right);
  if(node1!=NULL && node1->left==NULL && node1->right==NULL){
   return sumnodes++;
  }                 
  else
   return sumnodes;
}

I can understand simple recursive functions, but these binary search tree recursive functions are making me crazy!

uman · Apr 26th, 2005, 10:23 PM

Try this.

(Toggle Plain Text)

//UNTESTED!
int tree::sumLeaf(node* node1)
{
        if(node1 == NULL) return 0;
        if(node1->left == NULL && node1->right == NULL) return 1;
        else return sumLeaf(node1->left) + sumLeaf(node1->right);
}

BaroN NighT · Apr 26th, 2005, 10:27 PM

Damn dude, you rock! It prints 4, and yeah, the leaf nodes are 4 when I tried to draw the tree. Thx!

uman · Apr 26th, 2005, 10:28 PM

heh, no problem

Apr 26th, 2005, 9:48 PM	#1
BaroN NighT Programmer Join Date: Mar 2005 Location: USA Posts: 60 Rep Power: 4	Counting Number of Leaf Nodes Recursively(Binary Search Tree) I'm trying to write a function that counts the total number of leaf nodes in a binary search tree: (Toggle Plain Text) int tree::sumLeaf(node* node1) { int sumnodes = 0; if(node1==NULL){ return (0); } sumnodes=sumLeaf(node1->left); if(node1!=NULL && node1->left==NULL && node1->right==NULL){ return sumnodes++; } int tree::sumLeaf(node* node1) { int sumnodes = 0; if(node1==NULL){ return (0); } sumnodes=sumLeaf(node1->left); if(node1!=NULL && node1->left==NULL && node1->right==NULL){ return sumnodes++; } You can see that I'm trying to figure out to count it by going through all the way to the left first. Considering a binary search tree with the order of insertion: 15,7,85,10,2,99,66,50,43,15...the function should print 1 (for the leaf node containing the number 2). But it prints 0. Any help would be highly appreciated .

Apr 26th, 2005, 9:51 PM	#2
uman Expert Programmer Join Date: Dec 2004 Posts: 794 Rep Power: 4	(Toggle Plain Text) //UNTESTED! int tree::sumLeaf(node* node1) { if(node1 == NULL) return 0; return sumLeaf(node1->left) + sumLeaf(node1->right) + 1; } //UNTESTED! int tree::sumLeaf(node* node1) { if(node1 == NULL) return 0; return sumLeaf(node1->left) + sumLeaf(node1->right) + 1; }

Apr 26th, 2005, 10:12 PM	#5
BaroN NighT Programmer Join Date: Mar 2005 Location: USA Posts: 60 Rep Power: 4	I don't even know if this is right(now I'm trying to count all the leaf nodes,right and left, not like the first one above): (Toggle Plain Text) int tree::sumLeaf(node* node1) { int sumnodes = 0; if(node1==NULL){ return (0); } sumnodes=sumLeaf(node1->left); sumnodes=sumLeaf(node1->right); if(node1!=NULL && node1->left==NULL && node1->right==NULL){ return sumnodes++; } else return sumnodes; } int tree::sumLeaf(node* node1) { int sumnodes = 0; if(node1==NULL){ return (0); } sumnodes=sumLeaf(node1->left); sumnodes=sumLeaf(node1->right); if(node1!=NULL && node1->left==NULL && node1->right==NULL){ return sumnodes++; } else return sumnodes; } I can understand simple recursive functions, but these binary search tree recursive functions are making me crazy!

Apr 26th, 2005, 10:23 PM	#6
uman Expert Programmer Join Date: Dec 2004 Posts: 794 Rep Power: 4	Try this. (Toggle Plain Text) //UNTESTED! int tree::sumLeaf(node* node1) { if(node1 == NULL) return 0; if(node1->left == NULL && node1->right == NULL) return 1; else return sumLeaf(node1->left) + sumLeaf(node1->right); } //UNTESTED! int tree::sumLeaf(node* node1) { if(node1 == NULL) return 0; if(node1->left == NULL && node1->right == NULL) return 1; else return sumLeaf(node1->left) + sumLeaf(node1->right); }

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 26th, 2005, 9:56 PM	#3
BaroN NighT Programmer Join Date: Mar 2005 Location: USA Posts: 60 Rep Power: 4	Thank you for your prompt reply uman, but this function counts the total number of all the nodes, not the number of leaf nodes.

Apr 26th, 2005, 10:03 PM	#4
uman Expert Programmer Join Date: Dec 2004 Posts: 794 Rep Power: 4	whoops :-P. Sorry. Let me finish cleaning my room and I'll see what I can do.

Apr 26th, 2005, 10:27 PM	#7
BaroN NighT Programmer Join Date: Mar 2005 Location: USA Posts: 60 Rep Power: 4	Damn dude, you rock! It prints 4, and yeah, the leaf nodes are 4 when I tried to draw the tree. Thx!

Apr 26th, 2005, 10:28 PM	#8
uman Expert Programmer Join Date: Dec 2004 Posts: 794 Rep Power: 4	heh, no problem

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Counting Number of Leaf Nodes Recursively(Binary Search Tree)