How to depth first search through a collection of objects using recursion?

Question

The depth first search method I'm using to find a particular location by it's ID field, throws a Null pointer exception when looping through a list of location objects.

I debugged the error by setting a breakpoint on the findLocation() and dfs(), and it only fires the NPE in the dfs() for loop. So for example if I specify a location id of '1' the location will be returned correctly, but if I specify a location ID greater than 1 I get an NPE when the code steps into the dfs() for loop.

Does anyone know why the for loop is giving an NPE on any location ID greater than 1?, although the location ID's range from 1 - 10.

These are the two methods used in conjunction to find a location by ID:

public Location findLocation(Integer locationId) {
        Location result = null;
        for (Location l : location) {
            System.out.println("In find method...");
            result = dfs(new HashSet<Location>(), l, locationId); //line 180
            if (result != null)
                System.out.println("You are now in.." + result);
                break;
        }
        return result;
    }


private Location dfs(Set<Location> visitedAlready, Location current,
            Integer id) {
        if (current.id == id)
            return current;
        visitedAlready.add(current); 
        Location result = null;
        for (Location l : current.location) { //line 194
            result = dfs(visitedAlready, l, id);
            if (result != null)
                break;
        }
        return result;
    }

The exact error that is output is the following:

Exception in thread "main" java.lang.NullPointerException
    at gmit.Location.dfs(Location.java:194)
    at gmit.Location.findLocation(Location.java:180)
    at gmit.GameParser.parse(GameParser.java:55)
    at gmit.Main.main(Main.java:28)

Answer 1

It would be nice to know what the exact error message is, and so forth. For that matter, asking each dfs() to print current before continuing may be helpful.

There are two potential culprits: first, the passed argument current could be null, which will generate errors with current.id == id and current.location and even possibly visitedAlready.add(current) depending on what exactly that method tries to do with the argument. This could happen if the Location[] (or whatever the collection is) at current.location could have null entries.

The next is that current.location itself might be null or something that you can't pull Locations out of with a for-loop, so that Location l : current.location fails because current.location is not right. Indeed it sounds weird for a Location object to have a location property which contains its child nodes.

In general a recursive depth-first-search looks like this:

private Node findById(Set<Node> visited, Node root, Integer id) {
    int i; Node recurse;
    if (root.id == id) {
        return root;
    }
    visited.add(root);
    for (i = 0; i < root.children.length; i += 1) {
        recurse = findById(visited, root.children[i], id)
        if (result != null) {
            return result;
        }
    }
    return null;
}

If your code is not equivalent to that example you're going to have trouble.