n-Tree traversal from root node down to all childen

Question

I have a List with some tables from a database where each row contains a parent field refering to another row. Like this

title, parent
A, null
B, A
C, A
D, C
E, B
F, null

Here the A and F are root nodes, B and C is child to A, D is child to C and E is child to B in turn.

What is the best way to produce a tree structure from this list?

One way is to recurse over the list finding the root (the title without no parents) then for each root again loop over the list and attach the roots nodes. Then for those nodes again loop over the full list to attach any children of their own.

Example:

private Node getNode(SomeData d) {
    List<SomeData> tmp = getChildren(d);
    if (tmp == null OR empty) return new Node(d);

    Node n = new Node(d);
    for (SomeData m : tmp) {
        n.addChild(getNode(m)); // recurse
    }
    return n;
}

private List<SomeData> getChildren(SomeData parent) {
    List<SomeData> tmp = new ArrayList<SomeData>();
    for (SomeData candidateChild : myBigFlatDataList.values()) {
        if (parent.equals(candidateChild)) {
            tmp.add(candidateChild);
        }
    }
    return tmp;
}

Is there a better way to do this?

Answer 1

This is a pretty good way, but it is more naive than it has to be.

Another route takes just linear time. Is there something about a SomeData that uniquely identifies it? I would assume so; this could be SomeData itself implementing equals() and hashCode() properly.

Lets say there is a method int SomeData.getID(). Then we can keep Nodes we've previously seen in a HashMap.

Map<Integer, Node> visitedNodes = new HashMap...

Then we just read forward through the rows:

for ( SomeData data : ... ) {
    SomeData parent = data.getParent();
    Node<SomeData> parentNode = getOrCreateNode(parent);
    Node<SomeData> childNode = getOrCreateNode(data);
    parentNode.addChild(childNode);
}

private Node<SomeData> getOrCreateNode(SomeData data) {
    Node<SomeData> node = visitedNodes.get(data.getID());
    if ( node == null ) {
       node = new Node<SomeData>(data);
       visitedNodes.put(data.getID(), node);
    }
    return node;
}