I have an object

Node(String url, List<Node> children);

Now this could be several levels deep, ie

Node node1 = new Node ("www.google.com", new List<Node>())) (That list would contain more nodes, etc etc.

I want to traverse and flatten the tree, such that I can extract all the url values to a single list. I think I need recursion for this, however I can't work out how to do so.

CodePudding user response：

You can write a method which takes in Node and returns a list of nodes using recursion.

public List<Node> flattenNodes(Node node) {
    LinkedList<Node> nodes = new LinkedList<>();
    //recursively add the result of flattening children to nodes list
    node.getChildren().forEach(n -> {
        nodes.addAll(flattenNodes(n));
    });
    //add the current node to nodes list too
    nodes.add(node);
    return nodes;
}

This assumes the Node class has a getChildren method to get the children of the node as a list.

Here is node class I used when writing this solution:

public class Node {
    private final String url;
    private final List<Node> children;

    public Node(String url, List<Node> children) {
        this.url = url;
        this.children = children;
    }

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

    public String getUrl() {
        return url;
    }
}

I tested the solution using the following code:

Node aaa = new Node("www.aaa.com", new LinkedList<Node>());
Node aa = new Node("www.aa.com", List.of(aaa));
Node a = new Node("www.a.com", List.of(aa));
Node bb = new Node("www.bb.com", new LinkedList<Node>());
Node b = new Node("www.b.com", List.of(bb));
Node head = new Node("www.google.com", List.of(a, b));

flattenNodes(head).forEach(node -> System.out.println(node.getUrl()));

Running this test printed the following to console:

www.aaa.com
www.aa.com
www.a.com
www.bb.com
www.b.com
www.google.com

CodePudding user response：

The usual pattern you might use for problems like this is comparable with the ones to linked lists. If you want to search through a binary tree then you might add the left and the right child of each node as it´s class attributes and have functions which return you those nodes like this:

class Node
{
  Node leftChild;
  Node rightChild;
  string nodesUrl;

  // make the same function for right child
  public void setLeftChild(Node leftChild)
  {
    this.leftChild = leftChild;
  }

  // make the same function for right child
  public Node getLeftChild()
  {
    return leftChild;
  }

  // make here functions for setting and getting the node´s url
}

Since each node will have referenced it`s childs you can go for example as long to the left child, till you find the url you need. If you arrived at the end of the tree without success, you have to try each rightChild of each node you passed and repeat this process. This can be achieved by a recursive function, which is usually used to search through trees.

Node getNodeWithSearchingUrl(Node rootNode, string searchUrl)
{
  Node leftChild = rootNode.getLeftChild();
  Node rightChild = rootNode.getRightChild();

  Node foundNode = null;

  if(rootNode != null && rootNode.getUrl().Equals(searchUrl))
  {
    return rootNode;
  }
  
  if(leftChild != null)
  {
    foundNode = getNodeWithSearchingUrl(leftChild, searchUrl);
  }
  
  if(foundNode == null && rightChild != null)
  {
    foundNode = getNodeWithSearchingUrl(rightChild, searchUrl);     
  }

  return foundNode;
}

I did not try the code but I think it should work. If you have trees which are not binary but "multilevel", then instead of saving only the left and right child you need to save all children in a list and always run through the whole list with your recursive function.