How to convert a collection of categories into a tree structure

Question

I am doing a tree selector use p:multiSelectListbox. I have a collection of categories, and I tried to convert categories to a component supported structure(categories is unordered). Here is my category bean:

public class Category {
    private String id;
    private String pid; //parentId
    private String name;
    private String value;

    //getter and setter
}

This is my convert method:

public List<SelectItem> tree(List<Category> categories) {
    Map<Category, SelectItem> map = new HashMap<>();

    for (Category node : categories) {
        //Check if current category is leaf node, if true new SelectItem, else new SelectItemGroup
        SelectItem item;
        if (categories.stream().noneMatch(n -> node.getId().equals(n.getPid()))) {
            item = new SelectItem(node.getValue(), node.getName());
        } else {
            item = new SelectItemGroup(node.getName());
        }
        map.put(node, item);
    }
    //the result return
    //items just add the root level, and child level add into it's parent level
    List<SelectItem> items = new ArrayList<>();

    categories.forEach(node -> {
        //get parent category of current's
        SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null));

        //parent category is not exists, it's mean current category is root level
        if (item == null) {
            items.add(map.get(node)); //add root
        } else {
            SelectItemGroup parentGroup = (SelectItemGroup) item;
            SelectItem[] selectItems = parentGroup.getSelectItems();

            List<SelectItem> selectItemList = new ArrayList<>();
            if (selectItems != null) selectItemList.addAll(Arrays.asList(selectItems));
            //add current category into it's parent's children
            selectItemList.add(map.get(node));
            parentGroup.setSelectItems(selectItemList.toArray(new SelectItem[0]));
        }
    });

    return items;
}

When the categories's size is less than 10000, he works very well; if the size is greater than 20000, it becomes very slow. Does anyone know a more efficient way?

`categories.forEach(node -> { //get parent category of current's SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null))` ----------------these codes will have a O(n^2) time complexity — ZhaoGang, Dec 13 '18 at 07:19
I know it will have a O(n^2) time complexity. But I only have the relationship between pid and id. So I am looking for help to get an efficient method. — xmcx, Dec 14 '18 at 11:21
If my understanding is right, you are trying to make a tree structure from a list of categories, according to the `pid&id` relationship? Well this can be done with a `O(n)` time complexity using HashMap, IMHO. — ZhaoGang, Dec 14 '18 at 12:11
@ZhaoGang I tried to think up something can be done with O(n), but I couldn't. O(2n) is my the best. Could you share if you have O(n) solution please. — Ken Bekov, Dec 14 '18 at 18:44
https://stackoverflow.com/q/25777714/2830167 @KenBekov so yes I agree with your solution — ZhaoGang, Dec 14 '18 at 18:58
@ZhaoGang yes, you right. They both have a linear grouth. In that sense they are equal indeed. — Ken Bekov, Dec 14 '18 at 19:01

score 2 · Accepted Answer · answered Dec 15 '18 at 00:53

These codes will have a O(n^2) time complexity:

categories.forEach(node -> { //get parent category of current's SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null))

Making a tree structure from a list of categories, according to the pid&id relationship can be done with a O(n) time complexity using HashMap. Baic ideas described below.

Traverse the list of categories and put the pid&id mapping into a HashMap, time complexity:O(n). in the map we have(pid:List of children ids) as the Map.Entity. Now we actually have the tree structure already.
What we do next is to traverse the tree demonstrated via the hashmap, and get the result. It is this can be done either the recursion way which has been given by @Ken Bekov, or using an iterative way. The traveral procidure also takes O(n) time.

So the whole solution's time complexity is O(n). When the n is lagre, say 20000, it should be much faster than your original solution.

How to convert a collection of categories into a tree structure

1 Answers1