Return list of nodes. A tree in a Java parent can have multiple child nodes

Question

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

Node class

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

I try so. But unable to figure out how to write a loop to go through.

  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.

Answer 1

If you are sure that the structure is a tree (a node cannot have more than one parent), this will list the nodes in order of depth:

 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 the nodes can have multiple parents, change the first line of addAllNodes to:

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

The first algorithm is as follows:

 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; } 

Answer 2

You can use the “ Width Search ” or Depth Search .