In Binary Tree, find how many grandfathers have only two or three grandchildrens

Question

                                   8
                                /      \
                              4         12
                             / \         / \
                           3    6       2   1
                          / \   / \    /   / \
                         7  10 13 15  5   9  11
                                             /
                                            14 

I need to find the grandfathers of a tree, in this exemple I have only one grandfather, number 12 (I need that he has only two or three grandchildren) .

This is what I tried so far:

int T(struct node * tree){
    int t = 0;
    if (tree == NULL)
        return 0;
    if (tree->left && tree->right)
    {    //In this case i check if we NOT have all the four grandchildrens.
        if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right)))
        {
            t =  1 + T(tree->left) + T(tree->right);
            T(tree->left);
            T(tree->right);

        }
        else
       {
            T(tree->left);
            T(tree->right);
        }

    }

    return t;

}

Unfortunately it does not work... Can anyone help me with this?

Answer 1

One efficient approach is to recursively return a pair of results. There are more elegant ways to return a pair in C++, but I'll use the old kludgy C way of returning one output through an input by pointer:

int T2(struct node * tree, int* child_count)
{
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( tree->left )
    {
       ++ *child_count;
       t += T2( tree->left, &g );
    }
    if ( tree->right )
    {
       ++ *child_count;
       t += T2( tree->right, &g );
    }
    if ( g==2 || g==3 )
       ++t;
    return t; 
}

int T(struct node * tree) {int dummy; return T2(tree, &dummy); }

The function does two things together. The simple job is it helps count its parent's grandchildren by incrementing *child_count, and it also recursively does the main job by accumulating in t.

---

The following way might be easier to understand, but is less elegant:

int T(struct node * tree)
{
    struct node *c;
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( (c=tree->left) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( (c=tree->right) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( g==2 || g==3 )
       ++t;
    return t; 
}

Answer 2

This becomes easier if you introduce a couple of child-counting functions, one that counts children and one that counts grandchildren:

int children(node* tree)
{
   if (!tree)
   {
      return 0;
   }
   int count = 0;
   if (tree->left)
   {
      count += 1;
   }
   if (tree->right)
   {
      count += 1;
   }
   return count;
}

int grandchildren(node* tree)
{
   if (!tree)
   {
      return 0;
   }
   return children(tree->left) + children(tree->right);
}

int grandparents(node* tree)
{
   if (!tree)
   {
      return 0;
   }
   int count = grandchildren(tree);
   if (count == 2 || count == 3)
   {
       return 1 + grandparents(tree->left) + grandparents(tree->right);
   }
   else
   {
       return grandparents(tree->left) + grandparents(tree->right);
   }
}