Count the Nodes which are Left Childs in the Binary Tree

One way to ask this question is:

Given a Binary tree that represents a family hierarchy. A parent can have at most two children (at most one girl child and at most one boy child). A girl child (if present) is always represented as left child in the binary tree, and a boy child (if present) is always represented as the right child. There will never be a situation that a parent has 2 girl children or 2 boy children or have more then 2 children. Find the total number of girls in the family.

Another way to ask the same question is to directly ask,

Write a function that returns the total number of Nodes that are left child of their parents in a binary tree.

For example, Given the below binary tree, there are four girl children (B, D, H and F):

The catch in twisting the question ( as girl-child in family) is to see if you can make sense from ambiguous problems. Also, sometimes, in our code, we skip the check for left child of the right child (which need to be counted).

Solution:

The solution is fairly simple. We traverse the entire tree, and if a node has left child then we increment the number of girl children by one, else not.

Algo:

1. If root is NULL, then return 0.
2. If root does not have Left child
    - Return the number of left children in right-subtree.
3. Add the left children inside left and right subtree
   add 1 to it for the left-child of root
   and return the total sum

Code:

int countLeftChild(Node* r)
{
    if(r==NULL){ return 0; }
    if(r->lptr == NULL)
    {
        // NO Left child.
        return countLeftChild(r->rptr);
    }
    else
    {
        // Left child present.
        return countLeftChild(r->lptr) + countLeftChild(r->rptr) + 1;
    }
}