Recursively counting special nodes in a tree

Question

I built a tree consisting of nodes with each node having an attribute and a list of successors. I am trying to implement a recursive function which starts traversing the tree at a given node (in this example at the node "Method"). The function shall count the number of nested nodes with a given attribute. At the end, I want to return the highest number found within a single branch. Speaking of the given example, I would like to find the maximum amount of nested nodes with the attribute "Loop" which would be 3 (the according branch is marked orange).

Example: Currently, my approach looks like this:

private static int getLNDforMethod(DirectedNodeInterface curNode, int currentLND) {

    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        // isLoop returns true if the given node is a loop
        if(isLoop(curSuc))
        {
            ++currentLND;
        }

        currentLND = getLNDforMethod(curSuc, currentLND);
    }

    return currentLND;
}

The problem with this approach is that it is counting all loops within a given tree instead of just giving back the maximum number of a nested branch. So instead of returning 3 (which would be what I want) it returns 7 for the given example which equals the total number of "Loops" in the whole tree.

Apparently, I have some trouble thinking into recursive methods. Can anybody help me?

Answer 1

A very good strategy for thinking up recursive algorithms is to assume that you have already implemented your algorithm. In your case, it means assuming that you already have a function that finds the max for a single path.Your implementation boils down to calling the function for each child (remember, we're assuming it's already implemented), picking the max among them, and then either returning that max, or returning max plus one if our current node satisfies the condition.

The algorithm for finding the max count for a single path is as follows:

• Set max, the return value of your method, to 0
• Set own, the value added by the current node, to 0 if the desired attribute is absent or to 1 if the attribute is present in the current node
• Call getLNDforMethod for each child, and get childMax
• Set max to the maximum of max and own+childMax
• Return max

This is easier to express in Java code:

private static int getLNDforMethod(DirectedNodeInterface curNode) {
    int max = 0;
    int own = isLoop(curNode) ? 1 : 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        max = Math.max(max, own + getLNDforMethod(curSuc));
    }
    return max;
}

Answer 2

private static int getLNDforMethod(DirectedNodeInterface curNode) {

    int maxChild = 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        maxChild = Math.max(maxChild, getLNDforMethod(curSuc));
    }

    return maxChild + (isLoop(curNode) ? 1 : 0);
}