Showing the whole path of every Leaf in a Tree

Question

I wrote myself a quick Tree and Node class (nothing too fancy, doesn't have to do much). I have a variable number of next level nodes, I am using an ArrayList for those. It works like it is supposed to, the only problem is the toString() method. Example: I set it up with a bunch of numbers.

• 0 is root
• 0 has children 1,2,3
• 2 has children 2.4 and 2.5

Now, when I print out the tree, this is what I get: (slashes are supposed to be there)

• /0/1
• /2/2.5
• /2.4
• /3

What I want however is this:

• /0/1
• /0/2/2.5
• /0/2/2.4
• /0/3

this is my toString() :

public String toString() {
    String all = "";
    for (Node<T> node : nextNodes) {
        all += node.toString();
        if (node.isLeaf()) {
            all += "\n";
        }
    }
    return "/" + this.getNodeContent().toString() + all;
}

Could somebody please tell me what I have to change in order to walk from the root every time? Thanks!

Answer 1

How many paths are in some three? There are as many paths as many leaves - because that your code doesn't work. Code which you wrote only iterates through all nodes. But you want to print all paths from root to the leaves.

One solution is to use recursion: It starts from root and print path for every children. It look something like this

public void printPaths(Node<T> nodeOnPath, String onPath){
    String nodePath = onPath + "/" + nodeOnPath.getNodeContent().toString(); 
    if (nodeOnPath.isLeaf()){
        System.out.println(nodePath);
        return; 
    }

    ArrayList<Node> children = nodeOnPath.getChildren(); 
    for (Node<T> node : children){
        printPaths(node, nodePath); 
    }
}

Method for printing paths I named printPaths - it takes two arguments: the firs is node nodeOnPath and second is path from root to the node nodeOnPath. At the first line of method it creates nodePath. Then check if node is leaf - if answer is yes then print nodePath and exit from the method.

In case if the node is not leaf then get all children for the node, iterate through them and for every node generate path. This part is in for each loop.

To print all paths you will call method printPaths like this

printPaths(rootNode, "");

Answer 2

You need to add getNodeContent() to every childs path, here is a solution:

   public String toString() {
        String all = ""
        for (Node<T> node : nextNodes) {
            all += this.getNodeContent().toString() + node.toString();
            if (node.isLeaf()) {
                all += "\n";
            }
        }
        return "/" +  + all;
    }