Tree Traversal - Storing the Path

[Michael Grünau]

Hello Friends, its me again....back with another problem.

I am trying to write a method which goes through my tree, finds the element given to the function and gives back the path (nodes) I traversed while I was searching for that element/ object.

My Idea was to work with a few helper-methods to solve the problem.



1. Write a method to check if there is a path from each child of my current node.(There is always only one child-node option that works at each level)

    public boolean pathExists(Penguin penguin) {
        if(this.penguin.equals(penguin))
            return true;
        else {
            for(int i = 0; i < children.length;i++){
                if(children[i] != null)
                children[i].pathExists(penguin);
            }
            return false;
        }
    }

2. If there is a path I want to save the node and check the same thing for the child. I don't care about the nodes that don't have a path.

My questions now:

- Is there a smooth way to store the my paths? Thought about an ArrayList where I add the [i] that leads to the correct path.
- Does my pathExist function work? To be honest I am not even sure if i get the correct result that I want...

Hope this is not to vague and someone can maybe give me a Tip or send me a link to check a concept?
I only find Binary-Tree solutions.

Thank you very much in advance.

[Campbell Ritchie]

Are you asking how to traverse your tree or only how to record the nodes visited? If you are visiting the nodes recursively, one way to do that is to pass a List<Node> as an argument and add each Node visited to the List after the recursive call. It may be easier to add the nodes to a Stack implementation before the recursive call. Both those suggestions will show the leaf node first and the root last.

[Piet Souris]

I envisage something like:

public boolean pathExists(Penguin penguin, List<Node> nodes) {
    if(this.penguin.equals(penguin)) return true;
    else {
           for(int i = 0; i < children.length;i++){
               if(children[i] != null) {
                   nodes.add(children[i]);
                   if (!children[i].pathExists(penguin)) nodes.removeLast();
                   else return true;
               }
           }
           return false;
   }
}

Not tested!

[Michael Grünau]

That is correct.

My Helper-Method looks like this atm.

    public boolean pathExists(Penguin penguin) {
        if(this.penguin.equals(penguin))
            return true;

        for(int i = 0; i < children.length;i++){
            if(children[i] != null) {
                if(children[i].pathExists(penguin)) {
                    return true;
                }
            }
        }
            return false;
    }

Should I implement a List<Node> as an argument inside the helper-Method?

[Piet Souris]

Yes, if Nodes are clear enough to know what path they represent. You could also have a List<Integer> in wich the indices of a Child are stored. Whatever is most clear.

[Piet Souris]

I was just looking to see if we can fill that list from the end to the start, removing the need for a boolean result. The fact that the List is not empty is itself proof of the existence of a Path.

But then I saw this line of code:

if(this.penguin.equals(penguin))
           return true;

How do you start this method? It is an instance method, but in order to find the full path, you should invoke: root.findPath, or else get a partial path.

[Michael Grünau]

So the complete task for the Method was to find the Object in my tree, track the path and build the name via the tracked path.

Below is my complete approach:

    public String findName(Penguin penguin) {
        //Find an fill path
        ArrayList<Integer> nodes = new ArrayList<Integer>();
        boolean penguinExists = pathExists(penguin,nodes);
        //Translate Path to name
        String result = numberConversion(nodes);
        //Return if we found a penguin
        if(penguinExists)
            return result;
        else
            return null;
    }

    public String numberConversion(List<Integer> nodes) {
        char [] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
        StringBuilder sb = new StringBuilder();

        if(nodes.isEmpty())
            return "";
        else {
            for(int i = 0; i < nodes.size();i++) {
                int temp = nodes.get(i);
                sb.append(alphabet[i]);
            }
            String output = sb.toString();
            return output;
        }

    }

    public boolean pathExists(Penguin penguin, List<Integer> nodes) {
        if(this.penguin.equals(penguin))
            return true;

        for(int i = 0; i < children.length;i++){
            if(children[i] != null) {
                if(children[i].pathExists(penguin, nodes)) {
                    nodes.add(i);
                    return true;
                }
            }
        }
        return false;
    }

[Carey Brown]

I think you meant this

           for(int i = 0; i < nodes.size();i++) {
               int temp = nodes.get(i);
               sb.append(alphabet[i]);
           }

to be

           for(int i = 0; i < nodes.size();i++) {
               int temp = nodes.get(i);
               sb.append(alphabet[temp]);
           }