Convert java arrayList of Parent/child relation into tree? -

i have bunch of parent/child pairs, i'd turn hierarchical tree structures possible. example, these pairings:

child : parent     h : ga     f : g     g : d     e : d     : e     b : c     c : e     d : null     z : y     y : x     x: null 

which needs transformed (a) heirarchical tree(s):

   d     ├── e     │   ├──     │   │   └── b     │   └── c        └── g     |   ├── f     |   └── h     |     x     |     └── y         |         └──z 

how, in java, go arraylist containing child=>parent pairs, tree one?

i need output of operation arraylist contains 2 elements d , x in turn each 1 have list of children in turn contains list of children , on

public class megamenudto {     private string id;     private string name;     private string parentid;     private list<megamenudto> childrenitems=new arraylist<megamenudto>();      public string getid() {         return id;     }     public void setid(string id) {         id = id;     }     public string getname() {         return name;     }     public void setname(string name) {         this.name = name;     }     public string getparentid() {         return parentid;     }     public void setparentid(string parentid) {         this.parentid = parentid;     }     public list<megamenudto> getchildrenitems() {         return childrenitems;     }     public void setchildrenitems(list<megamenudto> childrenitems) {         this.childrenitems = childrenitems;     } } 

my first try was

private void arrangemegamenutree(megamenudto grandparent,         megamenudto parent, list<megamenudto> children) {      (megamenudto child : children) {         if (child.getparentid().equals(parent.getid())) {             arrangemegamenutree(parent, child, children);         }     }      if (!grandparent.getid().equals(parent.getid())) {         grandparent.getchildrenitems().add(parent);         // children.remove(parent);     }  } 

another try

private list<megamenudto> arrangemegamenutree(megamenudtoparent,list<megamenudto>menuitems) {      (megamenudto child : menuitems) {          if (parent.getid().equals(child.getid())) {             continue;         }         if (haschildren(child, menuitems)) {             parent.setchildrenitems(arrangemegamenutree(child, menuitems                     .sublist(menuitems.indexof(child), menuitems.size())));         } else {             list<megamenudto> templist = new arraylist<megamenudto>();             templist.add(child);             return templist;         }     }     return null; }  private boolean haschildren(megamenudto parent, list<megamenudto> children) {     (megamenudto child : children) {          if (child.getparentid().equals(parent.getid())) {             return true;         }     }     return false; } 

here alternative solution based on first answer , update of question ... :)

main method

import java.util.arraylist; import java.util.hashmap; import java.util.list; import java.util.map;  public class main2 {      public static void main(string[] args) {          // input         arraylist<pair> pairs = new arraylist<pair>();         pairs.add(new pair( "h" , "g"));         pairs.add(new pair( "f" , "g"));         pairs.add(new pair( "g" , "d"));         // ...           // arrange         // string corresponds id         map<string, megamenudto> hm = new hashmap<>();           // using megamenudto linked list next , before link           // populate map         for(pair p:pairs){              //  ----- child -----             megamenudto mmdchild ;             if(hm.containskey(p.getchildid())){                 mmdchild = hm.get(p.getchildid());             }             else{                 mmdchild = new megamenudto();                 hm.put(p.getchildid(),mmdchild);             }                        mmdchild.setid(p.getchildid());             mmdchild.setparentid(p.getparentid());             // no need set childrenitems list because constructor created new empty list                // ------ parent ----             megamenudto mmdparent ;             if(hm.containskey(p.getparentid())){                 mmdparent = hm.get(p.getparentid());             }             else{                 mmdparent = new megamenudto();                 hm.put(p.getparentid(),mmdparent);             }             mmdparent.setid(p.getparentid());             mmdparent.setparentid("null");                                           mmdparent.addchildrenitem(mmdchild);           }          // root         list<megamenudto> dx = new arraylist<megamenudto>();          for(megamenudto mmd : hm.values()){             if(mmd.getparentid().equals("null"))                 dx.add(mmd);         }          // print          for(megamenudto mmd: dx){             system.out.println("dx contains "+dx.size()+" : "+ mmd);         }      }  } 

pair class :

public class pair {     private string childid ;     private string parentid;      public pair(string childid, string parentid) {         this.childid = childid;         this.parentid = parentid;     }     public string getchildid() {         return childid;     }     public void setchildid(string childid) {         this.childid = childid;     }     public string getparentid() {         return parentid;     }     public void setparentid(string parentid) {         this.parentid = parentid;     }  } 

megamenudto class updated

import java.util.arraylist; import java.util.list;  public class megamenudto {      private string id;     private string name;     private string parentid;     private list<megamenudto> childrenitems;       public megamenudto() {         this.id = "";         this.name = "";              this.parentid = "";         this.childrenitems = new arraylist<megamenudto>();     }      public string getid() {         return id;     }     public void setid(string id) {         id = id;     }     public string getname() {         return name;     }     public void setname(string name) {         this.name = name;     }     public string getparentid() {         return parentid;     }     public void setparentid(string parentid) {         this.parentid = parentid;     }     public list<megamenudto> getchildrenitems() {         return childrenitems;     }     public void setchildrenitems(list<megamenudto> childrenitems) {         this.childrenitems = childrenitems;     }     public void addchildrenitem(megamenudto childrenitem){         if(!this.childrenitems.contains(childrenitem))             this.childrenitems.add(childrenitem);     }      @override     public string tostring() {         return "megamenudto [id=" + id + ", name=" + name + ", parentid="                 + parentid + ", childrenitems=" + childrenitems + "]";     }  }