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);
}

Answer 3

Your problem is that you're doing a breadth-first search without bothering to consider your own problem statement. What you want, is the maximum number of occurrences of LOOP in any branch but what you're doing is count all occurrences of LOOP in your entire tree. You can fix this by transforming your breadth-first search into a depth-first search or only returning the maximum of the result from your sub-recursive calls.

private static int GetLNDForMethod(DirectedNodeInterface curNode) {
    NodeIterator successors = curNode.getSuccessors();
    unsigned int numLnds = 0;
    while (successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        unsigned int curLnds = GetLNDForMethod(curSuc);
        if (isLoop(curSuc))
            curLnds++;
        if (numLnds < curLnds)
            numLnds = curLnds;
    }

    return numLnds;
}

What I did here was not a huge modification of your code, I merely inserted another variable and checked if it was greater than the current value and set the first if it was.

Note that since you (and I) only consider successors and do not examine the current node, this result will be one lower than the actual result if the root node is a LOOP