Count nodes with a specific number of children in a binary tree?
I have this tricky exercise I got from a book about C ++ and I'm not sure how to solve this problem. I have to define a function with a name treeNodeCount()
that returns the number of nodes in the binary tree (simple enough) and I also have to define an overloaded function that takes an int (0,1 or 2) that represents the number of children and the function should return the nodes y who have a certain number of children.
treeNodeCount
have to use a function called nodeCount(elemType root)
to perform the recursion needed to count the nodes (so basically all work).
call number one says that I can add a second parameter to nodeCount
that takes the number of children for the nodes we want to count.
Problem number two says we cannot use the second parameter (this is the tricky part)
I was able to make a call to one and this is what I came up with:
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p, int a ) const
{
if (p == NULL){
return 0;
}
else if (a == 0 && p->lLink == NULL && p->rLink == NULL){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == 1 && (p->lLink != NULL ^ p->rLink != NULL)){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == 2 && p->lLink != NULL && p->rLink != NULL){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == -1){
return nodeCount(p->lLink, a) + nodeCount(p->rLink, a) + 1;
}
return nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount(int a) const{
return nodeCount(root, a);
}
Everything seems to work fine, but I am convinced that there must be a better way. I was unable to make call 2 though, and I have no idea what to do (is it possible)
source to share
You can flatten your logic and make it simpler by implementing a function to return the number of children using node.
template <class elemType>
int nodeSize(nodeType<elemType>* node) const
{
int count = 0;
if (node->lLink)
++count;
if (node->rLink)
++count;
return count;
}
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType>* node, int count) const
{
if (node)
{
if (nodeSize(node) == count || count == -1)
return nodeCount(node->lLink, count) + nodeCount(node->rLink, count) + 1;
return nodeCount(node->lLink, count) + nodeCount(node->rLink, count);
}
return 0;
}
For the second task, you will need a stack to avoid recursion.
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount(int count) const
{
stack<nodeType<elemType>*> node_stack;
node_stack.push(root);
int num_matches = 0;
while (!stack.empty())
{
nodeType<elemType>* node = node_stack.top();
node_stack.pop();
if (node)
{
if (nodeSize(node) == count || count == -1)
++num_matches;
node_stack.push(node->lLink);
node_stack.push(node->rLink);
}
}
return num_matches;
}
Edit: Fixed a bug in the above recursive version. Thanks to David Rodriguez for pointing this out.
source to share