Jun 252015
 

The basic idea of DP is applicable to problems that can be thought in terms of recursion. For example, consider problem of computing n’th fibonacci term:

Fibonacci series Continue reading »

Jun 242015
 

One way to ask this question is:

Given a Binary tree that represent 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 total number of left node in a binary tree.

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

Binary_tree_ritambhara

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;
    }
}