Flatten a dynamic hierarchy tree by level

Question

I have a hierarchy tree that I retrieve on the fly (via REST services). I limit the data based on a depth and a limit of data I want. I want to flatten that tree based on the level, so first the children then the grandchildren, etc.

For example:

1
 -2
   -4
   -5
     -8
 -3
   -6
   -7
     -9

With a depth 100 and limit 100 it should be 2 3 4 5 6 7 8 9
With a depth 1 and limit 100 it should be 2 3
with a depth 2 and ​limit 5 it should be 2 3 4 5 6

Right now ​I have a recursive algorithm but it doesn't flatten by level but recursively (2 4 5 8 3 6 7 9).
Here is the actual code:

@GET
@Path("/GetDatas")
public Response getDatas(@QueryParam("clientId") final String clientId,
                           @QueryParam("maxDepth") final Integer maxDepth,
                           @QueryParam("limit") final Integer limit) {

    Set datas = new LinkedHashSet();

    findChildren(clientId, maxDepth, limit, datas, 0);

    return Response.status(Response.Status.OK).entity(datas).build();
}

private void findChildren(String clientId, Integer maxDepth, Integer limit, Set datas, Integer actualDepth)  {
    // here we are getting the data via a REST WS
    results = .... (function(clientId))

    for (final String result : results) {
        if (datas.size() < limit) {
            if (!datas.contains(result)) {
                datas.add(result);
                if (actualDepth < maxDepth) {
                    findChildren(result, maxDepth, limit, datas, actualDepth + 1);
                }
            }
        }
    }
}

I simplified a little bit. In fact, in reality a node will have himself as a grandchild too (the getChildren will retrieve matching datas based on a algorithm, so if 2 is a match for 1, 1 is the match for 2).

The order of the list is also important.

Here is the JDoodle so you can test: jdoodle.com/ia/gFm

Answer 1

The following mre uses BFS to flatten the tree, respecting the limits:

import java.util.*;

public class MyClass {

    public static void main(String[] args) {
        new DataClass().execute();
    }

    static class DataClass {

        public void execute() {

            Map<String, List<String>> tree = new LinkedHashMap();

            tree.put("1", Arrays.asList("2", "3"));
            tree.put("2", Arrays.asList("4", "5"));
            tree.put("3", Arrays.asList("6", "7"));
            tree.put("5", Arrays.asList("8"));
            tree.put("7", Arrays.asList("9"));
            tree.put("4", Arrays.asList());
            tree.put("6", Arrays.asList());
            tree.put("8", Arrays.asList());
            tree.put("9", Arrays.asList());

            int maxDepth =100, maxNodes =100;
            System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+ findChildren(maxDepth, maxNodes, tree));

            maxDepth =1; maxNodes =100;
            System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+ findChildren(maxDepth, maxNodes, tree));

            maxDepth =2; maxNodes =5;
            System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+findChildren(maxDepth, maxNodes, tree));
        }

        //helper method for bfs
        Set<String> findChildren(int maxDepth, int maxNodes,  Map<String, List<String>> tree)  {
            Set<String> flatTree = new LinkedHashSet<>(); //hold and return the flatten tree
            final String root = "1";
            List<String> nodesAtCurrentDepth = new ArrayList<>();//hold all nodes of the current depth
            nodesAtCurrentDepth.add(root);
            return findChildren(maxDepth,  maxNodes, 0, flatTree, nodesAtCurrentDepth, tree);
        }

        //flatten tree using bfs
        Set<String> findChildren(int maxDepth, int maxNodes, int currentDepth, Set<String> flatTree,
                List<String> nodesAtCurrentDepth, Map<String, List<String>> tree)  {

            if(currentDepth < maxDepth && ! nodesAtCurrentDepth.isEmpty()) {

                List<String> nodesAtNextDepth = new ArrayList<>();//collects all next level nodes
                //add all next depth nodes to nodesAtNextDepth, respecting maxNodes limit
                for(String node : nodesAtCurrentDepth){

                    for(String childNode : tree.get(node)){
                        if(flatTree.size() + nodesAtNextDepth.size() >= maxNodes) {
                            break;
                        }
                        nodesAtNextDepth.add(childNode);
                    }
                }

                flatTree.addAll(nodesAtNextDepth);
                currentDepth++;
                nodesAtCurrentDepth = new ArrayList<>(nodesAtNextDepth);
                findChildren(maxDepth,  maxNodes, currentDepth, flatTree, nodesAtCurrentDepth, tree);
            };

            return flatTree;
        }
    }
}

Output:

max depth:100 max nodes:100 - [2, 3, 4, 5, 6, 7, 8, 9]
max depth:1 max nodes:100 - [2, 3]
max depth:2 max nodes:5 - [2, 3, 4, 5, 6]