DFS: Finding the path to a node using depth first search (java)

Question

I have a tree. All nodes in this tree have some true/false value, an element, and parent/children pointers. One element in this tree has the true/false value set to true. I want to find a path (the sequence of elements) from the root to this unique node. So if my tree looked like this:

And the special node was H, my algorithm would return the string "ACEGH". I've implemented this using a DFS. However, my current algorithm is adding the elements of the nodes from the incorrect paths. So my current algorithm would return: "ABDCEFGHI".

private String dfs(Node node, String path) {

    if(node.special){
        return key;
    }

    for(Node n: node.children){
        if(n != null){
            path = path + n.element;
            dfs(n, path);
        }
    }
    return null;
}

Scott Hunter Scott Hunter · Accepted Answer · 2016-10-22T00:18:55

You need to remove n.element from the path if dfs returns null (interpreting that to mean that the solution path had not been found). You should also stop checking for children once dfs returns non-null.

For this to work, dfs should return non-null once it has found a path, regardless of what level it is at.

DFS: Finding the path to a node using depth first search (java)

1 Answers