Flattenned data into list of trees in java

For a list of the tree, you can store your data in a structure like this:

final class Node{ final int id; final string name; final List<Node> children; } 

So, the final structure is: List<Node>

The data structure you search for is called N-ary tree data structure (you can refer to wikipedia and nist).

If you are familiar with the binary tree (only two childs) , it will be easy for you to change fo n-ary tree (n childs).

In your case you have a forest of the n-ary tree (a list of the n-ary tree) , or you can consider it as one big tree with a common root, where all your effective tree begin at the level one.

The simplest way is to create a Node{info, listChildren} with a field info and a list (arrayList maybe) that will contain children, and a NTreeClasse that contain methods as addChild...generally we use a recursive function that check a certain condition to choose the right path where to insert a new node.

An example of implementing N-ary tree source code and binary tree source code example

If you want to improve your implementation or you seek optimisation, you have to consider some others points like:

• The type of the list of children in each node, which is related to the possible number of children, if the number is small we can use a simple array, if the number is big we can use hash table ... etc
• Is your tree change or not (dynamic with insert and delete)
• The traversal of the tree
• Avoid recursion: replace the recursive method by an iterative.
• Consider the construction steps, the normal way is for each element, we begin from the root, and we find the right path til we arrive to the leaf where we should insert the node (new child), you can maybe insert the children directly in the right place, its depend on your data and how you want to organize your tree.
• you can consider using array to store the tree, also depend strongly on your data.

Hope this helps a little bit to begin and to dig further.

I am providing you a short and straight forward algorithm. It's the dirty version. You can rewrite it as you wish(by which, i mean a better version):

I am assuming, there is a table array such that table[i].activityID would give me ith activity's id and table[i].parentID would give me the activity's parent id ans so on...

[Note: one more point here, I'm also assuming if there is no parent of an element then, its parent id is -1, i.e. in the given example of yours a1's and a3's parent id would be -1. This way we can understand which activity does not have any parent. If you have a better idea, you can use that].

Let us first define the class Activity

class Activity implements Comparable<Activity> { int id; String name; List<Activity> children; Activity(int id, String name) { this.id = id; this.name = name; this.children = new ArrayList<>(); } @Override public int compareTo(Activity activity) { return this.id - activity.id; } } 

As the activity class is defined, we'll be creating activity's now and put them in a TreeMap(just to keep track of them).

Notice, which activity's parent id is -1, those will be roots of trees [and according to your example, there could be several trees formed from your table]. We'll keep track of roots while creating activity's.

// to keep track of all acticities TreeMap<int, Activity> activities = new TreeMap<>(); for(int i=0; i<table.length; i++) { Activity a = new Activity(table[i].activityID, table[i].activityName); activities.add(a); } // to keep track of root activities List<Activity> roots = new ArrayList<>(); for(int i=0; i<table.length; i++) { // check if there is a parent of this Activity Activity activity = activities.get(table[i].activityID); // now, if activity has a parent // then, add activity in the parent's children list if(table[i].parentID != -1) { Activity parent = activities.get(table[i].parentID); // this is very bad way of writing code // just do it for now // later rewrite it parent.children.add(activity); } else { // and activity does not have a parent // then, it is a root roots.add(activity); } } 

Now, we're going to create a traverse method, which will help to traverse the tree node in order.

void traverse(Activity u) { System.out.println(u.name); for(Activity v: u.children) { traverse(v); } } 

Now, you can call this function using the root activities:

for(Activity rootActivity: roots) { traverse(rootActivity); } 

That's it...