CODEWITHSUNDEEP
javalisttreeparenttraversal
rapadura
rapadura

Reputation: 5300

n-Tree traversal from root node down to all childen

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?

Upvotes: 1

Views: 2895

Answers (5)

Ashis Kumar
Ashis Kumar

Reputation: 11

List<User> list = new ArrayList<User>();
User blankNode;
class User{
    String userid;      
    User child;     
    public User() {
        //blankNode 
    }
    public User(String userid) {
        this.userid = userid; 
    }
    @Override
    public int hashCode(){
        return userid.hashCode();
    }
}
public void addUser(User parent,String userid){
    if(null == userid)return;
    User child = new User(userid);
    parent.child = child;
    list.add(child);        
}
public void removeUser(User child){
    if(null == child)return;        
    list.remove(child);
}
/* move the rank to up - assume
 * secParent - assign to new child
 */
public void boubbleUp(User secParent,  User oldParent, User child){
    if(null == child || null == secParent)return;
    secParent.child = child;
    oldParent.child = null;
}
public List<User> getTopUser(int num){
    if(num <1)return null;
    Map<Integer, List<User>> map = new HashMap<Integer, List<User>>();
    for(User usr : list){
        int count =0;
        User temp = usr.child;
        while(null != temp){
            count++;temp=temp.child;
        }           
        if(map.get(count)== null){
            List<User>  sameNoOfChildren = new ArrayList<User>()    ;
            sameNoOfChildren.add(usr);
            map.put(count, sameNoOfChildren);
        }else{
            map.get(count).add(usr);                
        }
    }
    Integer[] arr = (Integer[]) map.keySet().toArray();
    Arrays.sort(arr);
    List<User> result = new ArrayList<User>();
    for(int i = arr.length-1; i <=arr.length-num; i-- ){
        result.addAll(map.get(i));
    }       
    return result;      
}

Upvotes: 1

slosd
slosd

Reputation: 3474

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

Upvotes: 1

Mark Peters
Mark Peters

Reputation: 81074

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

Upvotes: 1

Keith Randall
Keith Randall

Reputation: 23265

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).

Upvotes: 1

Sagar V
Sagar V

Reputation: 1926

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.

Upvotes: 1

Related Questions