Question
Write a method called countEmpty that returns the number of empty branches in a tree. An empty tree is considered to have one empty branch (the tree itself). For nonempty trees, your methods should count the total number of empty branches among the nodes of the tree. A leaf node has two empty branches, a node with one nonempty child has one empty branch, and a node with two nonempty children has no empty branches.
Add the above method to the IntTree class from this chapter. You may define additional private methods to implement your public method if necessary. Several problem descriptions refer to the following reference binary trees:
For example, reference tree #1 has 7 empty branches (two under the value 1, one under 5, and two under each of 4 and 6.)
Answer
public int countEmpty()
{
return countEmpty(overallRoot);
}
private int countEmpty(IntTreeNode root)
{
if(root == null)
return 0;
if(root.left == null && root.right == null)
{
return 2 + countEmpty(root.left)
+ countEmpty(root.right);
}
else if(root.left == null || root.right == null)
{
return 1 + countEmpty(root.left)
+ countEmpty(root.right);
}
else
{
return countEmpty(root.left)
+ countEmpty(root.right);
}
}