# Thread: counting leafs

1. ## counting leafs

is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?

2. is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?
Just do a depth first search on the tree returning the number of leaves and nonleaves.

3. how would I do that?

4. Well, before you can program it, you have to define it-- tie the idea down to something.

Question: What makes a leaf?
Question: What makes a non-leaf?

In any given binary tree, you can only have two (2) types of nodes-- either a parent node, or a child (leaf) node. The difference between the two (2) is simple:

parents have either a left-child, a right-child, or both. Leaf (child) nodes have no children hanging off of them.

Use recursion to start at the root (first parent node) and walk the left children until there are not, then try a right child and start trying for more left children. Eventually it will traverse all children in the tree and return when it's back to the root node.

Here's some pseudo-code:

Code:
```/* Structures */
typedef struct nodeStrucPtr                         /* makeup of a node */
{
struct nodeStrucPtr *leftChild;
struct nodeStrucPtr *rightChild;
}leafNodeRec,*leafNodePtr;

/* Prototypes */
int main(void);                                              /* entry/exit point */
void treewalk(leafNodePtr);                         /* recursive part */

/* Global variables */
leafNodePtr  rootNodeP;                              /* root of b-tree */
int                 leaf_counter = 0;                    /* counters */
int                 nonleaf_counter = 0;

/* Functions & Procedures */

int main(void)
{
/* we assume the tree is already allocated  & populated */
/* if not, do that here                                                       */

treewalk(rootNodeP);                           /* go count nodes */

return(0);
}

void treewalk(leafNodePtr leafP)
{
if(!leafP)                                                    /* pointer valid? */
return;                                                   /* ... no, bail */

if(leafP->leftChild)
treewalk(leafP->leftChild);                     /* down left child */
if(leafP->rightChild)
treewalk(leafP->rightChild);                  /* down right child */

if(leafP->leftChild || leafP->rightChild)     /* leaf or parent? */
nonleaf_counter++;
else
leaf_counter++;
}```
Rather than going out for effeciency, I used more code so it would be more understandable.

Popular pages Recent additions