DFS: Finding the path to a node using depth first search (java)
<p>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:</p>

<pre><code>     A
    / \
   B   C
  /     \
 D       E
        / \
       F   G
          / \
         H   I
</code></pre>

<p>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".</p>

<pre><code>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;
}
</code></pre>