1,105,534 Community Members

Is this segment of code right or wrong?

Member Avatar
vuquanghoang
Newbie Poster
17 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I'm going to have a lecture about Tree, in the slide have a piece of code like that

public int iPathLength(int level) {
        return level + this.getLeft().iPathLength(level + 1)
                + this.getRight().iPathLength(level + 1);

I think this function is wrong since as I concern, recursive function have to have a base case to quit the recursive loop. Please help me to figure out the problem :(

Member Avatar
thekashyap
Practically a Posting Shark
809 posts since Feb 2007
Reputation Points: 193 [?]
Q&As Helped to Solve: 77 [?]
Skill Endorsements: 0 [?]
 
0
 

Problem is exactly what you pointed out. A recursive function without a "break condition". In this case if getLeft() or/and getRight() is NULL then you shouldn't call .iPathLength() on it, thus breaking the recursion.

Theoretically it might still be possible to make this code itself work (using specialized derived classes to act as leaf nodes without any children, which have a different impl for iPathLength() , instead of NULL). But it would be over-engineering IMO and especially irrelevant in classroom.

Member Avatar
vuquanghoang
Newbie Poster
17 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Thank u for your repky. As what you have mention, it means when the recursive function will automatically break and return value when leaf child or right child is null, right? So this code is right?

Member Avatar
Momerath
Senior Poster
3,832 posts since Aug 2010
Reputation Points: 1,327 [?]
Q&As Helped to Solve: 664 [?]
Skill Endorsements: 19 [?]
Featured
 
0
 

No, it's not right. In most cases it will generate an exception (null reference) unless you have a specialized 'leaf' node that implements different code for iPathLength (for example, some implementations of Red-Black trees use a specialized leaf node).

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article