Hi, I'm trying to put together a recursive function to count number of internal nodes, but I can't seem to grasp how to just grab internals. Any help? This so far only seems to count number of nodes

int numI(Node* p)
{
if(p== NULL)
  return 0;
else
return 1+numI(p->left)+numI(p->right);
}

Edited 5 Years Ago by DoinWork: n/a

return 1+numI(root->left)+numI(root->right);

needsto be

return 1+numI(p->left)+numI(p>right);

Sorry, That was simple typing error just now. That isn't the issue however, It simply counts every node, not just internals.

there are 2 def's for internal one with root one with out :
1-With root:

numI(Node* p)
{
if(p== NULL)
  return 0;
else
{
int sum=numI(p->left)+numI(p->right);
if(sum)
{
sum+=1;
}
return sum;
}
}

2-WithOut root:

int numI(Node* root)
{
int sum = numIExt(root);
if(sum)
sum=-1;
return sum;
}
int numIExt(Node* p)
{
if(p== NULL)
  return 0;
else
{
int sum=numI(p->left)+numI(p->right);
if(sum)
{
sum+=1;
}
return sum;
}
}

FYI:that in case you cannot check for parent

I tried #1, and it returns 0 instead of 4. Numbers in list I have are entered 5,8,3,12,15,7.

I'm assuming by internal node you mean all nodes except the leaf nodes? If so then possibly give this a try( haven't tested it )

bool hasLeftChild(const Node*const p){
 return p->left != NULL;
}
bool hasRightChild(const Node* const p){
 return p->right != NULL;
}
bool isLeaf(const Node* const p){
 return !hasLeftChild(p) && !hasRightChild(p)
}

int countInternalNode(const Node*const p){
 if(p == NULL | isLeaf(p)) return 0;
 else return 1 + countInternal(p->left) + countInternal(p->right);
}

EDIT: modularized a little

Edited 5 Years Ago by firstPerson: n/a

This article has been dead for over six months. Start a new discussion instead.