Find all descendants deeply of tree structure from flat data

I have a flat data that represent the hierarchical relationship as below:

ID Name PID
0 A NULL
1 B 0
2 C 0
4 D 1
5 E 1
6 F 4
3 G 0


This table represents the 'data table', where PID indicates the parent element.
For example, in the first row we see that A has PID null whereas B has PID 0, which means that B’s parent is A, because 0 is the ID of A, and A is the root element, because it does not have a PID. Similarly, C has parent A because C too has PID 0, and 0 is the ID of A.

I create a class RecordHolder to represent the above table. I also implement the method processRecordHolder

public Map> processRecordHolder()


The returned map uses element as keys, and holds collections of descendant nodes as values. For example, the first item in the map corresponds to element A, which has many descendants, whereas element C has no descendant. The order of members in the output is not important.

public static void main(String[] args) {

RecordHolder dt = newRecordHolder();

dt.addRow(0, "A", null);
dt.addRow(1, "B", 0);
dt.addRow(2, "C", 0);
dt.addRow(4, "D", 1);
dt.addRow(5, "E", 1);
dt.addRow(6, "F", 4);
dt.addRow(3, "G", 0);

System.out.println("Output:");
System.out.println(dt.processRecordHolder());
}

Output:
{D=[F], A=[B, C, G, D, E, F], B=[D, E, F]}
or
{D=[F], E=null, F=null, G=null, A=[B, C, G, D, E, F], B=[D, E, F], C=null}


Below is my implementation of RecordHolder:

`public class RecordHolder {

private List records = new ArrayList<>();
private Map indexes = new HashMap<>();
private static final int PROCESSORS = Runtime.getRuntime().availableProcessors();

/**
* Add new record into RecordHolder.
*
* @param id
* @param name
* @param parentId
*/
public void addRow(Integer id, String name, Integer parentId) {
if (indexes.get(id) == null) {
Record rec

I think what you're missing here is an algorithmic change to improve the way you load data, ranter than the way you compute the results.

One way to do this would be to build a tree to store your Records. A tree is really not that complicated to do, but, there's an in-between thing you can do which will really help.

Create a Map> as part of the constructor of your class. Call it tree for want of a better name. Then, each time you add a record, ensure that the tree is modified as well. Here's your current method:

public void addRow(Integer id, String name, Integer parentId) {
    if (indexes.get(id) == null) {
        Record rec = new Record(id, name, parentId);
        records.add(rec);
        indexes.put(id, records.size() - 1);
    }
}

If we change that to be:

private final Map> tree = new HashMap<>();

public void addRow(Integer id, String name, Integer parentId) {
    if (indexes.get(id) == null) {
        Record rec = new Record(id, name, parentId);

        records.add(rec);
        indexes.put(id, records.size() - 1);

        // Special note here!!!
        tree.put(id, new ArrayList<>());
        if (parentId != null) {
            tree.get(parentId).add(Id);
        }

    }
}

Note how we simply add the data to the tree structure. The special note I have there is that the above code only supports input data where the parentID is always added before any child Id's that use that parent. If the data comes in a different order, it will fail with a NullPointerException. There are ways to alter the code to create a "phantom" record for parents that have not been added before, though. Since your example data is compatible with my suggestion, though, I'll leave that up to you.

Now, once you have that tree structure right, the way to get all the descendents of a node, is simple:

List children = new ArrayList<>();
children.addAll(tree.get(id));
for (int i = 0; i < children.size(); i++) {
    children.addAll(tree.get(children.get(i)));
}

That style of loop is needed because we modify the children List while iterating over it (so the children.size() keeps on increasing).

I hope that gives you some ideas.

StackExchange Code Review Q#93289, answer score: 3