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);
}``````

## All 6 Replies

``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

Solved it myself, Thanks anywho. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.