Determine the Internal Path Length of a Tree (C++)

Question

Well I'm down to the last function of my program and I'm done. I've hit another stump that I can't seem to fix on my own.

int Tree::InternalPathLength(Node * r, int value)
{
    if(r->left == NULL && r->right == NULL)
    {
        return 0;
    }
    return value + InternalPathLength(r->left, value+1) + 
        InternalPathLength(r->right, value+1);
 }

I feel like i'm close to the solution, but i know i'm missing something. I think it's another if statement and i've tried different combinations but i end up getting a crashed program or 0 for the answer.

Any suggestions or help would be much appreciated ! thanks!

Answer 1

May be this works:

int Tree::InternalPathLength(Node * r, int value)
{
    if(r->left == NULL && r->right == NULL)
    {
        return 0;
    }
    return value + ( r->left? InternalPathLength(r->left, value+1):0 )
                 + ( r->right? InternalPathLength(r->right, value+1):0 );
 }

or just add NULL check for NODE

int Tree::InternalPathLength(Node * r, int value)
{
    if (r == NULL ) return 0;
    if(r->left == NULL && r->right == NULL)
    {
        return value +1;
    }
    return value + InternalPathLength(r->left, value+1) + 
        InternalPathLength(r->right, value+1);
 }

Answer 2

maybe you can pass in the value counter as reference? then increment it every time the function is called ? idk .. i am working on a program due tomorrow as well that needs this same function...

Answer 3

if(r == NULL) 
{
    return 0;
}
return (value+InternalPathLength(r->right,value+1)+InternalPathLength(r->left,value+1));

I finally got it!

Thanks for your help though!