n-Tree traversal from root node down to all childen

Question

Hello

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

Since you get the data from a DB you can sort the rows according to the parent attribute. Then you wouldn't need to iterate over the whole list everytime you search for the children of a node.

EDIT: When the list is sorted you can stop iterating over the list when you found all children you were looking for. For example when you have the root "A" and you start searching for its children in this list:

B, A
C, A
E, B  <- when you reach "B" you can assume that there are no
D, C     other nodes which are children of "A" and stop the iteration

Answer 2

Re-reading the entire file (or worse querying the database) for every node is rather expensive. I would rather you build the tree as you read the list. Here's my 2 cents

1. Let Nodes be a set of Nodes (initially an empty set).
2. Let RootNodes be a set of all Root Nodes (initially an empty set).
3. For every pair of nodes (N1,N2):
   
   1. For each N in (N1,N2) if N not in Nodes, create N and insert into Nodes.
   2. If N2 == null, also insert N2 into RootNodes (additionally you could also delete it from Nodes)
   3. Mark N2.child = N1.

If you follow this, at the end of the iteration over the list you should have:

RootNodes = {A,F}
Nodes = {B,C,D,E}

A.child = B
A.child = C
C.child = D
B.child = E

Hope this helps.

Answer 3

You can build your tree all at once. You can do a first pass over the table to build all of the nodes (build a hashtable from name to Node), then do another pass where you can add parent-child relationships between two Nodes (add parent pointer to child and add child to list of children in the parent).

Answer 4

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;
}