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

Recommended Answers

All 3 Replies

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.

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.