0
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.