segmentation fault in recursion

Question

i am trying to learn tree with C. i need to find longest path. i am using recursive approach for this. but i am getting segmentation fault. i am not able to find why it is happening. i dont need logic. i want to do it on my own. just want to know what basic fault I am doing.

Any suggestion for handling pointers is most welcome.

void longestPath(struct node *p,int *maxlen,int count)
{
    if(p==NULL)
        return;

    count++;

    if(p->lft==NULL && p->rt==NULL )
    {
        if(*maxlen<count)
             *maxlen=count;
    }

    longestPath(p->lft,maxlen,count);
    longestPath(p->rt,maxlen,count); 
}

Shouldn't p->lft==NULL && p->rt==NULL be p->lft==NULL || p->rt==NULL? — Kerrek SB
– Kerrek SB, Commented Jan 1, 2014 at 16:40
Run in a debugger. It might be that you don't set the leaf nodes left or right pointers to NULL. — Some programmer dude
– Some programmer dude, Commented Jan 1, 2014 at 16:41
I agree with @self. I can't see any wrong thing in your function. Provided that it is called with a valid tree and valid pointer for maxlen, this should work. I also think that it's not || but && as you have put it, because you want to detect when you have come to the end of a branch. — mcleod_ideafix
– mcleod_ideafix, Commented Jan 1, 2014 at 16:49

TimDave · Accepted Answer · 2014-01-01 16:56:29Z

2

Check maxlen for NULL also. That is likely the problem you are dereferecing the pointer without validating it.

int maxpath = 0;
int count = 10; // for example
struct node* nodes; // initialized somewhere else
longestPath( nodes, &maxpath, count );

edited Jan 1, 2014 at 16:56

answered Jan 1, 2014 at 16:43

TimDave

6503 silver badges6 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2696466 Over a year ago

thanks TimDave. it was same you said. was not using malloc. sometimes it works without malloc also. do you have any idea why. should i be always passing pointer only after malloc?

TimDave Over a year ago

You can declare the variable on the stack and pass its address instead of using malloc. See edited post for example.

wildplasser · Accepted Answer · 2014-01-01 16:50:02Z

1

Instead of passing the result via a pointer, you could use the return value:

unsigned longestPath(struct node *p)
{
    unsigned ll,rr;

    if (!p) return 0;

    ll = longestPath(p->lft);
    rr = longestPath(p->rt);

    return ll > rr ? 1+ll : 1+rr;
}

answered Jan 1, 2014 at 16:50

wildplasser

44.5k9 gold badges72 silver badges116 bronze badges

Collectives™ on Stack Overflow

segmentation fault in recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related