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 :(

4 Years
Discussion Span
Last Post by Momerath

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.

Edited by thekashyap: n/a


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?


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).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.