Return list of Nodes a Tree in Java-Parent can have multiple child Nodes

Question

I am trying to write java code to return list of Nodes in a tree. The tree looks like

Node class is

class Node{
 String label;
 List<Node> children;
}

I am trying this way. But not able to understand how to write a loop to traverse.

    public List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = 
        new ArrayList<Node>();
    boolean iterationCompleted = false;
    if(node==null){
        return null;
    }
    while(!iterationCompleted){
    if(node.getChildren()==null){
        listOfNodes.add(node);
                    break;    
    }
            else{
               //
            }
    }
    return null;
    //return traverseAndReturnAllNodes(node.getChildren().get(0));
}

Please help.

Respective

You will need to recurse (you could, say, have a stack of Nodes for where you are, but that's not so elegant). Each iteration of the while look (posh for loop would be better) should add the child node and addAll the list from the recursive call to get the child node's descendents. (There are some changes you can make to get the lists back in different orders.) – Schutzstaffel

Answer 1

If you're certain that the structure is a tree (a node cannot have more than one parent), this will list the nodes in depth-first order:

public static List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = new ArrayList<Node>();
    addAllNodes(node, listOfNodes);
    return listOfNodes;
}

private static void addAllNodes(Node node, List<Node> listOfNodes) {
    if (node != null) {
        listOfNodes.add(node);
        List<Node> children = node.getChildren();
        if (children != null) {
            for (Node child: children) {
                addAllNodes(child, listOfNodes);
            }
        }
    }
}

If nodes can have several parents, change the first line of addAllNodes to:

    if (node != null && !listOfNodes.contains(node)) {

The breadth-first algorithm goes like this:

public static List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = new ArrayList<Node>();
    if (node != null) {
        listOfNodes.add(node);
        for(int i = 0; i < listOfNodes.size(); ++i) {
            Node n = listOfNodes.get(i);
            List<Node> children = n.getChildren();
            if (children != null) {
                for (Node child: children) {
                    if (!listOfNodes.contains(child)) {
                        listOfNodes.add(child);
                    }
                }
            }
        }
    }
    return listOfNodes;
}

Leftwards

Answer 2

You can use Breadth-first search or Depth-first search.

Barkentine

Answer 3

As a enhancement to Maurice Perry's answer for DFS based approach. In case child nodes are alone needed (as parent node is already known), then instead of adding the node always to listOfNodes, child node can alone be added as

public static List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = new ArrayList<Node>();
    addAllNodes(node, listOfNodes);
    return listOfNodes;
}

private static void addAllNodes(Node node, List<Node> listOfNodes) {
    if (node != null) {
        List<Node> children = node.getChildren();
        if (children != null) {
            for (Node child: children) {
                listOfNodes.add(child);
                addAllNodes(child, listOfNodes);
            }
        }
    }
}

Stirk