java create multiple tree like structure using parent id from flat file

Question

I have data like below

CategoryId  CategoryName  CategoryParentId
123         XYZ           111
111         ABC           
222         PQR           
555         DEF           111
321         IJK           222

If you see this a unordered data read from a flat file which can be in any order.

I want to create trees like below:

111
|  \
123 555  

and

222
\
321

I have this data in an object, which looks like below:

public class Category {
    private String id = null;
    private String name = null;
    private String parentId = null;

    public Category(String id, String name, String parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

I am trying to process this data to create list of categories tree.

public class CategoryTree {
    private String name     = null;
    private String id       = null;

    private CategoryTree<String, CategoryTree> children = new TreeMap<String, CategoryTree>();


    public CategoryTree() {
    }

    public CategoryTree(String name, String id) {
        setName(name);
        setId(id);
    }

    public TreeMap<String, CategoryTree> getChildren() {
        return this.children;
    }

    public CategoryTree getChild(String childId) {
        return this.children.get(childId);
    }

    public void setChild(CategoryTree child) {
        this.children.put(child.getId(), child);
    }

    public boolean hasChild(String childId) {
        TreeMap<String, CategoryTree> set = this.children;
        boolean result =  set.containsKey(childId);
        return result;
    }
}

Below is what I am trying to do:

public void processData(List categoryList) {
    List<CategoryTree> roleObjectList = new ArrayList<CategoryTree>();

    Iterator<Category> itr = categoryList.iterator();
    while (itr.hasNext()) {
        Category entry = itr.next();
        String id = entry.getId();
        String name = entry.getName();
        String parentId = entry.getParentId();

        // i am confused here
        // CategoryTree parent = new CategoryTree(name,  id);
           parent.addChild(entry);
    }
}

I am confused on this part. How to start the tree. Since entry in the first iteration of loop has parent but it's parent is not present in the final list yet. How to add first entry to it's parent.

Answer 1

It seems that the parent.id < child.id holds, that is: the parent is created first. Though not necessary, that condition could sometimes ease things.

Here it is not needed.

public void processData(List<Category> categoryList) {
    Map<String, CategoryTree> map = categoryList.collect(
            Collectors.toMap(cat -> cat.id,
                             cat -> new CategoryTree(id, name)));
    List<CategoryTree> treeRoots = new ArrayList<>(); // Forrest if more than one root.
    categoryList.forEach(cat -> {
        CategoryTree node = map.get(cat.id);
        if (cat.parentId != null) {
            CategoryTree parent = map.get(cat.parentId)
            parent.children.add(node );
        } else {
            treeRoots.add(node );
        }
    });
    List<CategoryTree> roleObjectList = new ArrayList<>(map.values());
    ...

Though maybe faster than a path following algorithm (that could exploit the id order), it needs additional memory: an extra map.

Answer 2

You can build your tree recursively. First step will be to extract the roots of your trees. Then create a function who get the direct children of each node by running on the list (O(n)) - inside there will be recursive call for each of the children.

I guess my JAVA syntax is little but rusty so this is the pseudo code:

function getChildren(nodeID, listOfNodes):
    childrenList = empty list 
    for each node in listOfNodes:
        if node.parentId == nodeID: // if node is direct child
            node.children = getChildren(node.id, listOfNodes); //recursively get all his children 
            childrenList.add(node) // add it to the children list
    return childrenList;

main:
     listOfNodes = get list from your file
     listOfRoots = init empty list
     for each node in listOfNodes:
         if (node.parentId is empty) //not parent
             listOfRoots.add(node)
     // now listOfRoots is has all the roots
     for each node in listOfRoots:
         node.children = getChildren(node.id, listOfNodes)

This will be in O(n^2) complexity. 2 immediate improvement you can do is save the listOfNode in object and used it as this so you won't need to overload the memory. Second, you can modify the list each time and remove the node that assign (as he cannot be assign twice...)

Hope that helps!