Member Avatar for vuquanghoang

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

  • 3 Contributors
  • 3 Replies
  • 138 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Momerath
Member Avatar for thekashyap

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 because: n/a
Member Avatar for vuquanghoang

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 for Momerath

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.