How to count the leaves of a tree without a outside function counter?

Question

I got bombed in a interview because I was asked to write an algorithm which would count the leaves of a tree, I did this:

class TreeNode{
TreeNode[] children;
int value;

ctor(){
 children = new TreeNode[]();
}
}

class CountingClass{
int count;

ctor(){
count = 0;
}

void Count(TreeNode node)
{
 if(node.Children.Count > 0)
 {
   foreach(TreeNode item in node.Children)
   {
     Count(item);
   }
 }
 count++;
}


}

the interviewer appreciated demostrating my OOP approach but he wanted a solution contained in the function.

I got nervours and gave up after 20 minutes figuring it out. I was trying to pass an int as ref in the param but he said that is not what he was looking for either.

What is that thing I am missing here?

Answer 1

You can count the leaves of the tree via a simple recursive function. Implement count_leaves(TreeNode node) as follows:

• If node.children is empty, return 1 as this node is a leaf itself
• Otherwise, return the sum of count(child) for all child in node.children

No external counters or complicated passing is needed.