Get the parent path of Node in a tree

Question

I am using the following code to convert a flat structure like:

test/test2/test3
test/test5/test2
test/test7/test5/test4
test/test7/test5/test9

into a tree like:

        test
|        |      |
test2   test5   test7
|        |      |
test3   test2   test5
                |        |
                test4    test9

The code:

import java.util.*;
class Tree
{
    class Node
    {
        String data;
        ArrayList<Node> children;

        public Node(String data)
        {
            this.data = data;
            children = new ArrayList<Node>();
        }

        public ArrayList<Node> getChildren()
        {
            return children;
        }

        public Node getChild(String data)
        {
            for(Node n : children)
                if(n.data.equals(data))
                    return n;

            return null;
        }
    }

    private Node root;

    public Tree()
    {
        root = new Node("");
    }

    public boolean isEmpty()
    {
        return root==null;
    }

    public void add(String str)
    {
        Node current = root;
        StringTokenizer s = new StringTokenizer(str, "/");
        while(s.hasMoreElements())
        {
            str = (String)s.nextElement();
            Node child = current.getChild(str);
            if(child==null)
            {
                current.children.add(new Node(str));
                child = current.getChild(str);
            }
            current = child;
        }
    }

    public void get()
    {
        return root;
    }
}

I use the "add" function to split the above flat paths to a tree and it works nicely and I am able to navigate forward. Though, I want to be able to navigate to the Node with a given path and also when I navigate to some Node, I want to be able to trace it to the root element. For example, if I navigate from test -> test2 -> test3, I want to get the path from the root like test/test2/test3.

I am new to Trees and the topic is confusing me a bit, your help is highly appreciated.

Edit: Added a visual representation.

Answer 1

public class Tree {

    private final Node root = new Node(null, null);

    public boolean isEmpty() {
        return root.children.isEmpty();
    }

    public void add(String path) {
        Node parent = root;

        for (String data : path.split("/")) {
            Node node = parent.getChild(data);

            if (node == null)
                parent.children.add(node = new Node(data, parent));

            parent = node;
        }
    }

    public Node get(String path) {
        Node parent = root;

        for (String data : path.split("/")) {
            Node node = parent.getChild(data);

            if (node == null)
                return null;

            parent = node;
        }

        return parent;
    }

    public static final class Node {

        private final String data;
        private final Node parent;
        private final List<Node> children = new LinkedList<>();

        public Node(String data, Node parent) {
            this.data = data;
            this.parent = parent;
        }

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

        public Node getChild(String data) {
            for (Node node : children)
                if (node.data.equals(data))
                    return node;

            return null;
        }

        public String getPath() {
            Deque<String> nodes = new LinkedList<>();
            Node node = this;

            while (node.parent != null) {
                nodes.addFirst(node.data);
                node = node.parent;
            }

            return String.join("/", nodes);
        }

        @Override
        public String toString() {
            return data;
        }
    }

    public static void main(String... args) {
        Tree tree = new Tree();
        tree.add("test/test2/test3");
        tree.add("test/test5/test2");
        tree.add("test/test7/test5/test4");
        tree.add("test/test7/test5/test9");

        Node node = tree.get("test/test7/test5/test9");
        String path = node.getPath();
    }

}

Answer 2

A simple way is to keep track of the parent node, then just follow the parents up the tree from the child:

Node currentNode = ...
ArrayList<Node> path = new ArrayList<>();
while(currentNode != null){
    path.add(currentNode);
    currentNode = currentNode.getParent();
}
Collections.reverse(path);

So your Node class would need a new constructor:

class Node {
    String data;
    ArrayList<Node> children;
    Node parent;
    Node(Node parent, String data){
        // ...
    }
    // ...
    // Null if this is the root, else returns the parent node
    public Node getParent(){ return parent; }
}