Getting all possible paths in a tree structure

Question

I need to loop in a tree to get all possible paths, the problem in my code that i get just the first path!

example:

In the figure, there are 2 paths t handle: 1-2-3-4-5-6 and 1-2-3-7-8 , but i couldn't get both, i have just retrieved 1-2-3-4-5-6 !

my code:

In main:

for (String key : synset.keySet()) { // looping in a hash of Concept and it's ID
        System.out.println("\nConcept: " + key + " " + synset.get(key));
        List<Concept> ancts = myOntology.getConceptAncestors(myOntology.getConceptFromConceptID(synset.get(key))); // this function retreives the root of any node.

        for (int i = 0; i < ancts.size(); i++) {
            System.out.print(ancts.get(i).getConceptId() + " # ");
            System.out.print(getChilds(ancts.get(i).getConceptId()) + " -> "); // here, the recursive function is needed to navigate into childs.. 
        }
        System.out.println("");
    }

Rec. function:

public static String getChilds(String conId)
{
    List<Concept> childs = myOntology.getDirectChildren(myOntology.getConceptFromConceptID(conId)); // get all childs of a node
    if(childs.size() > 0)
    {
        for (int i = 0; i < childs.size(); i++) {
            System.out.print( childs.size() + " ~ " + childs.get(i).getConceptId() + " -> ");
            return getChilds(childs.get(i).getConceptId());
        }
    }
    else
        return "NULL";
    return "final";
}

Answer 1

I didn't really see enough of your code to use the classes that you have defined. So I went for writing my own working solution.

In the following code, the problem is solved using recursion:

public class TreeNode {
    private String id;
    private TreeNode parent;
    private List<TreeNode> children;

    public TreeNode(String id) {
        this.id = id;
        this.children = new LinkedList<>();
    }

    public void addChild(TreeNode child) {
        this.children.add(child);
        child.setParent(this);
    }

    public List<TreeNode> getChildren() {
        return Collections.unmodifiableList(this.children);
    }

    private void setParent(TreeNode parent) {
        this.parent = parent;
    }

    public TreeNode getParent() {
        return this.parent;
    }

    public String getId() {
        return this.id;
    }
}

public class TreePaths {
    private static List<List<TreeNode>> getPaths0(TreeNode pos) {
        List<List<TreeNode>> retLists = new ArrayList<>();

        if(pos.getChildren().size() == 0) {
            List<TreeNode> leafList = new LinkedList<>();
            leafList.add(pos);
            retLists.add(leafList);
        } else {
            for (TreeNode node : pos.getChildren()) {
                List<List<TreeNode>> nodeLists = getPaths0(node);
                for (List<TreeNode> nodeList : nodeLists) {
                    nodeList.add(0, pos);
                    retLists.add(nodeList);
                }
            }
        }

        return retLists;
    }

    public static List<List<TreeNode>> getPaths(TreeNode head) {
        if(head == null) {
            return new ArrayList<>();
        } else {
            return getPaths0(head);
        }
    }
}

To use the above code, a tree must be constructed using the TreeNode class. Start off by creating a head TreeNode, then add child nodes to it as required. The head is then submitted to the TreePaths getPaths static function.

After getPaths checks for null, the internal getPaths0 function will be called. Here we follow a depth first approach by trying to get to all leaf nodes as soon as possible. Once a leaf node is found, a List only containing this leaf node will be created and returned inside the list collection. The parent of this leaf node will then be added to the beginning of the list, which will again be put into a list collection. This will happen for all children of the parent.

In the end, all possible paths will end up in a single structure. This function can be tested as follows:

public class TreePathsTest {
    TreeNode[] nodes = new TreeNode[10];

    @Before
    public void init() {
        int count = 0;
        for(TreeNode child : nodes) {
            nodes[count] = new TreeNode(String.valueOf(count));
            count++;
        }
    }

    /*
     * 0 - 1 - 3
     *       - 4
     *   - 2 - 5
     *       - 6
     *       - 7 - 8
     *           - 9
     */
    private void constructBasicTree() {
        nodes[0].addChild(nodes[1]);
        nodes[0].addChild(nodes[2]);
        nodes[1].addChild(nodes[3]);
        nodes[1].addChild(nodes[4]);
        nodes[2].addChild(nodes[5]);
        nodes[2].addChild(nodes[6]);
        nodes[2].addChild(nodes[7]);
        nodes[7].addChild(nodes[8]);
        nodes[7].addChild(nodes[9]);
    }

    @Test
    public void testPaths() {
        constructBasicTree();
        List<List<TreeNode>> lists = TreePaths.getPaths(nodes[0]);
        for(List<TreeNode> list : lists) {
            for(int count = 0; count < list.size(); count++) {
                System.out.print(list.get(count).getId());
                if(count != list.size() - 1) {
                    System.out.print("-");
                }
            }
            System.out.println();
        }
    }
}

This will print out:

0-1-3
0-1-4
0-2-5
0-2-6
0-2-7-8
0-2-7-9

Note: The above is enough for manual testing, but the test function should be modified to do proper assertions for proper automated unit testing.