title: Depth first search list paths to all end nodes
body: <p>Hi I have a tree in which I would like to get paths from the initial (root) node to all leaves.</p>
  
  <p>I found several algortithms that list (all) apths betwenn any given two nodes within a graph (for example this SO question: 
  <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices">Graph Algorithm To Find All Connections Between Two Arbitrary Vertices</a>)</p>
  
  <p>For binary tree there also exists an algorithm 
  <a href="http://techieme.in/print-all-paths-in-a-tree/" rel="nofollow noreferrer">http://techieme.in/print-all-paths-in-a-tree/</a>
  but I work on a tree with various branching factors.</p>
  
  <p>Is there any better way of achieving what I want to do than traversing the tree once in order to get all leaves and then run the algorithm above for all leaves combined with the initial node?</p>
  
  <p>I was thinking about implementing simple DFS extended by some additional stack containing all nodes alongt he path to a single leaf and then listing all sentences by looping through these stacks.</p>
  
  <pre><code>    ArrayList&lt;GrammarNode&gt; discovered = new ArrayList&lt;GrammarNode&gt;();
      Stack&lt;GrammarNode&gt; S = new Stack&lt;GrammarNode&gt;();
  
  
      while (!S.empty()) {
          node = S.pop();
          if (!discovered.contains(node)) {
              discovered.add(node);
              System.out.println(node.getWord.getSpelling().trim());
              for (GrammarArc arc : node.getSuccessors()) {
                  S.push(arc.getGrammarNode());
              }
          }
      }
  </code></pre>
  
  <p><strong>UPDATE:</strong>
  The problem of this is that one has alyways go back to the root in order to generate full sentences. So I guess the question is: How to remember the node which was already fully visited (this means where all children nodes were already explored)?</p>