Convert java arrayList of Parent/child relation into tree?

Question

I have a bunch of parent/child pairs, that I'd like to turn into hierarchical tree structures as possible. So for example, these could be the pairings:

Child : Parent
    H : Ga
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL
    Z : Y
    Y : X
    X: NULL

Which needs to be transformed into (a) heirarchical tree(s):

   D
    ├── E
    │   ├── A
    │   │   └── B
    │   └── C   
    └── G
    |   ├── F
    |   └── H
    |
    X
    |
    └── Y
        |
        └──Z

How, in Java, would I go from an arrayList containing child=>parent pairs, to a Tree like that one?

i need the output of this operation is arrayList contains two elements D and X in turn each one have list of its children which in turn also contains a list of children and so 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) {

    for (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) {

    for (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) {
    for (MegaMenuDTO child : children) {

        if (child.getParentId().equals(parent.getId())) {
            return true;
        }
    }
    return false;
}

what is your first attempt of code please ? how you intend to represent the Tree in java ? — , Jun 01 '15 at 09:44
by Tree i mean Element have a list of elements and each element of them contain lit of elements and so on — Melad Basilius, Jun 01 '15 at 10:02
sorry to bother you , but please no need to communicate all your getters and setters , be more precise as possible. — , Jun 01 '15 at 10:17
the solution http://stackoverflow.com/a/30570416/813853 seems legit ! — , Jun 01 '15 at 10:17

score 10 · Answer 1 · answered Jun 01 '15 at 09:52

10

Suppose your Node structure is something like:

class Node {
  Object id;
  List<Node> children;
  Node parent;

  public Node(Object id) {
    this.id = id;
    children = new LinkedList<>();      
  }
}

Then you first start iterating on your input list, and create a map from ids->Nodes (this is used to fetch the nodes while the tree is still unstructured);

Map<Object, Node> temp = new HashMap<>();
for (Pair pair: inputList) {
  Node parent = temp.getOrDefault(pair.parent.id, new Node(pair.parent.id));
  Node child = temp.getOrDefault(pair.child.id, new Node(pair.child.id));
  parent.children.add(child);
  child.parent = parent;
  temp.put(parent.id, parent);
  temp.put(child.id, child);
}

Now you can iterate on your map searching for the root of your tree

for (Node n: temp.values()) {
  if (n.parent==null) {
    root = n; break;
  }
}

This code assumes that your data is "valid" (no duplicated children entries, single root, etc.) You can easily adapt it otherwise.

answered Jun 01 '15 at 09:52

Diego Martinoia

4,592
1
17
36

Since we do a lot of `get` we better use `ArrayList` then `LinkedList` , check this I may be wrong http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Jun 01 '15 at 10:27
I just took the first collection that I could think of. It's more likely that the children should be a set rather than a list. Or if you need some additional info on the link, you could have a map from ID to Info. I didn't have other info to make a more informed choice (my code doesn't do a single get on the list of children :) – Diego Martinoia Jun 01 '15 at 10:37
sorry, I was looking at my code ... (saw get and comment ) – Jun 01 '15 at 10:40
precise solution Thanks – Melad Basilius Jun 02 '15 at 13:48

score 6 · Accepted Answer · 2015-06-01T14:42:53.697

Here is an alternative solution based on the first answer and the update of the 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 to the Id
        Map<String, MegaMenuDTO> hm = new HashMap<>();


        // you are using MegaMenuDTO as Linked list with next and before link 

        // populate a 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 to set ChildrenItems list because the constructor created a 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);


        }

        // Get the 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()+" that are : "+ 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 + "]";
    }

}

This solution will give you stack overflow exception if your input contains the root also input : H : Ga F : G G : D E : D A : E B : C C : E D : D Please be cautious about input. — Ajay Jayavarapu, Oct 07 '16 at 07:04
I have to go to one step before the pairs. As I have one common list in which every entry contains parent id and I have to make pairs first before I go into this solution. — Ravi Yadav, Aug 02 '19 at 06:51
@MeladBasilius Hi, How can i adopt this to recylerview? Would you help me? — Handelika, Oct 23 '20 at 15:39

score 3 · Answer 3 · answered Jul 03 '20 at 10:56

Try this

Simply hash it on the basis of your id's and build your relationship.

Find the root of the tree once it's done.

    private MegaMenuDTO getRoot(Map<String, MegaMenuDTO> tree) {
        return tree.values().stream().filter(node -> Objects.isNull(node.getParentId())).findFirst().orElse(null);
    }

    public MegaMenuDTO createTree(List<MegaMenuDTO> list) {
        Map<String, MegaMenuDTO> tree = new HashMap<>();
        list.forEach(current -> tree.put(current.getId(), current));
        list.forEach(current -> {
            String parentId = current.getParentId();
            if (tree.containsKey(parentId)) {
                MegaMenuDTO parent = tree.get(parentId);
                current.setParentId(parentId);
                parent.addChildrenItem(current);
                tree.put(parentId, parent);
                tree.put(current.getId(), current);
            }
        });
        return getRoot(tree);
    }

score 0 · Answer 4 · edited Nov 02 '18 at 06:07

depending on @Diego Martinoia solution and @OSryx solution ,the final solution to my problem

private List<MegaMenuDTO> dooo(List<MegaMenuDTO> input) {
    Map<String, MegaMenuDTO> hm = new HashMap<String, MegaMenuDTO>();
    MegaMenuDTO child = null;
    MegaMenuDTO mmdParent = null;

    for (MegaMenuDTO item : input) {

        // ------ Process child ----
        if (!hm.containsKey(item.getId())) {
            hm.put(item.getId(), item);
        } 
        child = hm.get(item.getId());

        // ------ Process Parent ----
        if (item.getParentId() != null && !item.getParentId().equals("")
                && !item.getParentId().equals("0")) {
            if (hm.containsKey(item.getParentId())) {
                mmdParent = hm.get(item.getParentId());
                mmdParent.getChildrenItems().add(child);
            }
        }

    }

    List<MegaMenuDTO> DX = new ArrayList<MegaMenuDTO>();
    for (MegaMenuDTO mmd : hm.values()) {
        if (mmd.getParentId() == null || mmd.getParentId().equals("")
                || mmd.getParentId().equals("0"))
            DX.add(mmd);
    }
    return DX;
}

I don't believe this will work if your nodes are ordered randomly or bottom up in your list. You'll have a bunch of orphan nodes that wont link to its parents. For example, the first node to get processed will not have its parent in the map so it will always be orphaned. — patelb, Jul 17 '19 at 17:37

score 0 · Answer 5 · edited Jan 28 '19 at 09:37

Here is my solution:

Convert MegaMenuDTO list to map :

public static  Map<String, MegaMenuDTO> buildIdMap(Collection<MegaMenuDTO> targets){
    Map<String, MegaMenuDTO> result = new HashMap<>();
    if(targets!=null && !targets.isEmpty()){
        final Iterator<MegaMenuDTO> iterator = targets.iterator();
        while (iterator.hasNext()){
            final MegaMenuDTO next = iterator.next();
            if(StringUtils.isNotBlank(next.getId())){
                result.put(next.getId(),next);
            }
        }
    }
    return result;
}

then convert the map to tree:

public List<MegaMenuDTO> getTree(List<MegaMenuDTO> all ){
    final List<MegaMenuDTO> result = new ArrayList<>();
    final Map<String, MegaMenuDTO> allMap = buildIdMap(all);
    final Iterator<MegaMenuDTO> iterator = all.iterator();
    while (iterator.hasNext()){
        final MegaMenuDTO next = iterator.next();
        final String parentId = next.getParentId();
        if(StringUtils.isNotBlank(parentId)){
            final MegaMenuDTO node = allMap.get(next.getId());
            final MegaMenuDTO nodeP = allMap.get(parentId);
            if(nodeP != null){
                nodeP.getChildren().add(node);
            }
        }else{
            next.setOpen(true);
            result.add(next);
        }
    }
    return result;
}

Convert java arrayList of Parent/child relation into tree?

5 Answers5

Main Method

Pair class :

MegaMenuDTO Class Updated

Linked