Java: how to recursively fill a tree node

Question

For a project I want to generate a tree structure which has x children and is n 'layers' deep. A layer can the best be described in the following figure:

                  0
           1            1
        2     2      2     2

The number on each row equals the layer number.

I got the following class named Node:

public class Node {

    private String nodeName;
    private List<Node> children;
    private int layer;

    /**
     * A node with a name and a list of children on a given layer in a tree or
     * web
     *
     * @param nodeName the name of the node
     * @param children the list of children of this node
     * @param layer the layer in which this node exists
     */
    public Node(String nodeName, List<Node> children, int layer) {
        this.nodeName = nodeName;
        this.children = children;
        this.layer = layer;
    }
}

Additionally, I have getters and setters for each field.

After struggling for two full evenings, I came up with this code:

private static Node createTree() {
        Node masterNode = new Node();
        int childsPerNode = 3;
        int amountOfLayers = 5; //meaning 6 layers, 0 is included
        //Output = 364
        int totalNodeAmount = calculateNodeAmount(childsPerNode, amountOfLayers);

        //Loop for each layer, form bottom to top
        for (int currentLayer = 5; currentLayer > amountOfLayers; currentLayer--) {
            /**
             * For each layer, calculate the nodes for this layer, add children
             * to each node
             */
            int nodesThisLayer = calculateNodeAmount(childsPerNode, amountOfLayers) - calculateNodeAmount(childsPerNode, currentLayer);
            for (int nodeCount = 0; nodeCount < nodesThisLayer; nodeCount++) {
                List<Node> children = new ArrayList<>();
                for (int childCount = 0; childCount < childsPerNode; childCount++) {
                    String childFunctionName = "name";
                    Node childNode = new Node(childFunctionName, null, currentLayer);
                    children.add(childNode);
                }
                String parentFunctionName = "parent name";
                Node parentNode = new Node(parentFunctionName, children, currentLayer);
            }

        }
        return masterNode;
    }

Any help regarding my way to end up with one Node which contains the whole tree in its children is greatly appreciated, as I'm out of ideas. I did not find a good source for a tree with x children and n layers (or depth), hence my potential double question.

Kind regards!

EDIT: Based on the comment of lexicore, I came up with this function:

 private static void createTree(Node currentNode, int childrenPerNode, int numberOfLayers) {
    if (numberOfLayers == 0) {
        //Something is off here
        return;
    } else if (numberOfLayers > 0) {
        //Create sub nodes
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < childrenPerNode; i++) {
            Node childNode = new Node("name", nodes, numberOfLayers);
            nodes.add(childNode);
        }
        //Add the children to the current node
        currentNode.setChilderen(nodes);
        for (int i = 0; i < childrenPerNode; i++) {
            //For each of the children per node, call this function again until the number of layers equals zero
            createTree(currentNode.getChildren().get(i), childrenPerNode, numberOfLayers - 1);
        }
    }

This does, however, continue too loop way too 'deep' (too much layers). I'm breaking my head on why that is.

I'll be looking to the other answers right now. Thanks for your time already!

Answer 1

Here's an example of a fully encapsulated object-oriented design (i.e. recursive constructor):

public class Tree
{
    private int layer;
    private int nodeID;
    private List<Tree> children;

    public Tree(int numOfchildren, int numOfLayers)
    {
        this(numOfchildren, numOfLayers, 0, new int[1]);
    }

    private Tree(int numOfchildren, int numOfLayers, int layerIndex, int[] nodeIndex)
    {
        layer = layerIndex;
        nodeID = nodeIndex[0]++;

        if (numOfLayers > 0 && numOfchildren > 0) {
            children = new ArrayList<Tree> ();
            for (int i = 0; i < numOfchildren; i++) {
                children.add(new Tree(numOfchildren, numOfLayers - 1, layer + 1, nodeIndex));
            }
        }
    }
}

Some noteworthy concepts:

• The Tree class contains one public constructor and one private constructor. The public constructor in just a "clean" interface. The private one does all the "dirty" work.
• The layerIndex parameter of the private constructor sets the offset of the root node. Setting it to 0 (as does the public constructor) is best.
• The int[] nodeIndex array parameter of the private constructor is a "workaround" for sending an int argument by reference. The array argument (as provided by the public constructor) consists of a single element array that keeps track of the number of children created thus far in order to set the nodeID to a unique value.

Answer 2

This is obviously not the best design, but a pretty brief solution:

int childsPerNode = 3;
int amountOfLayers = 5;

class AutoNode {

    int layer;
    List <AutoNode> childs;

    public AutoNode (int n) {
        layer = n;
        if (layer < amountOfLayers) {
            childs = new ArrayList<AutoNode> ();

            for (int i = 0; i < childsPerNode; ++i) {
                childs.add (new AutoNode (n + 1));
            }
        }
    }
    public String toString () {return ("layer: " + layer + " <" + ((layer < 5) ? childs.toString () : "()") + ">" );}
}

AutoNode root = new AutoNode (0);

The bounds:

int childsPerNode = 3;
int amountOfLayers = 5;

are somewhat alien to the Nodes. But it works as a first, quick prototype.

You can add methods to the Autonode, and perform different exercises. You may put them as final static into the Autonode definition.

If you want to heat up System, call root with = new AutoNode (-40); but calculate 3^45 first.

Answer 3

The title says "recursive," so I'll assume you really want to write a recursive method. To write one, you must learn to think recursively.

For the task of building trees, this is pretty straightforward. Trees are recursively defined: a tree may be empty or else a node with trees as children.

In your case the definition is a bit more complicated. A layer N tree may be empty (if N is greater than or equal to the max desired layer number) or else it's a node with layer number N and K subtrees with layer number N+1.

This translates to an algorithm:

Node buildTree(int N) {
  // A layer N tree may be empty (if N is more than the max desired layer number)
  if (L >= maxLayerNumber) {
    return new Node with no children
  }
  // ... or else it's a node with layer number N and K subtrees with layer number N+1
  Let C be an initially empty list of children
  for i = 1 to K {
    Let c = buildTree(N + 1)  
    Add c to C
  }
  return new Node with layer number N and children C
}

To get the whole tree, call buildTree(0).

I'm deliberately not providing Java code. It's important to solve problems yourself.

Answer 4

You might want to avoid calculating the number of children you'll need to create by either using recursion as suggested in the comments or by iterating through the bottom nodes of the tree and keeping them in a separate collection.

List<Node> children = new ArrayList<Node>(); 
children.add(masterNode);
int layer = amountOfLayers;

while (layer > 0) {
  List<Node> allBottomChildren = new ArrayList<Node>();
  for (Node child : children) {
    List<Node> nextLevelChildren = new ArrayList<Node>();
    for (int i = 0;i<childsPerNode;i++) {
      Node node = new Node("name", new ArrayList<Node>(), layer - 1);
      nextLevelChildren.add(node);
    }
    child.setChildren(nextLevelChildren);
    allBottomChildren.addAll(nextLevelChildren);
  }
  children = allBottomChildren;
  layer = layer - 1;
}