Create child nodes using recursion

Question

I'm trying to create a hierarchy from flat data. I have the following Node definition:

public class Node {
        public String name;
        public List<Node> children = new ArrayList<>();
    }

Given this data: [Person,Manager,Hourly,New], where the tree should be like:

Person
  |--Manager
       |--Hourly
            |--New

I've tried the following:

public void run()
    {
        List<List<String>> objects = new ArrayList<>();

        String[] str = {"Person","Manager","Hourly","New"};
        objects.add(Arrays.asList(str)) ;

        String[] str2 = {"Person","Manager","Salary"};
        objects.add(Arrays.asList(str2)) ;

        String[] str3 = {"Person","Manager","Salary", "New"};
        objects.add(Arrays.asList(str3)) ;

        // Create a Node with the sequence
        myNode = new Node();
        createNode(objects.get(0), 0, myNode, myNode);
        LOG.debug(myNode.name);
}

And my createNode method is:

public Node createNode(List<String> seq, Integer start, Node parentNode, Node childNode)
    {
      // do something and return a Node?
    }

But conceptually I don't understand how to maintain the structure if Java is return-by-value. What do I add to createNode so that I can add a Manager->Hourly->New hierarchy as a child to Person

Answer 1

You don't need both a Node return type and a Node argument to your method.

Here's one way to do it:

//in run()
myNode = new Node();
myNode.name = "Root";
createNode(objects.get(0), 0, myNode, myNode);



public void createNode(List<String> seq, Integer start, Node parentNode)
{
    Node childNode = new Node();
    childNode.name = seq[start];
    parentNode.children.Add(childNode);
    createNode(seq, start+1, childNode);
}

You don't need to return anything from createNode() -- since you have parentNode as a variable, you can add things to its children member. A call to createNode() will recursively add child nodes, following your string array to its end.

Another way to do it is like this:

public Node createNode(List<String> seq, Integer start)
{
    if (start >= seq.Length) {
        return null;
    }
    Node node = new Node();
    node.name = seq[start];
    node.children.Add(createNode(seq, start+1);

    return node;
}

In this case, you don't need to pass in node references at all; calling createNode() will generate a new node object, fill its children tree recursively, and return the newly-generated node structure.