smihael - 1 year ago 111

Java Question

Hi I have a tree in which I would like to get paths from the initial (root) node to all leaves.

I found several algortithms that list (all) apths betwenn any given two nodes within a graph (for example this SO question:

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices)

For binary tree there also exists an algorithm

http://techieme.in/print-all-paths-in-a-tree/

but I work on a tree with various branching factors.

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?

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.

`ArrayList<GrammarNode> discovered = new ArrayList<GrammarNode>();`

Stack<GrammarNode> S = new Stack<GrammarNode>();

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

}

}

}

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)?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Printing all paths from the root to every leaf would mean to print the entire tree so I'd just use a simple DFS and do the following for each node:

- add it to the list/stack
- if the node has children, repeat for the children
- if the node is a leaf, print the list/stack
- pop the node from the list/stack

Example:

```
A
/ \
B E
/ \ / \
C D F G
```

The first steps would look like this:

- put A on the list -> {A}
- put B on the list -> {A,B}
- put C on the list -> {A,B,C}
- since C is a leaf, print the list (A,B,C)
- remove C from the list -> {A,B}
- put D on the list -> {A,B,D}
- since D is a leaf, print the list (A,B,D)
- ...

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**