Convert hierarchical list to a flat list in java

Question

I have a hierarchical list like below and I want to convert it to a flat list.

I have wrote a method called convertToFlatList and have used it. But some elements are missing in the final results. What did i do wrong?

Also is there a better way than the way I have used to convert my list to a flat list?

I have added a sample code and something similar to the Objects I have to used in my scenario. Final result should be 1, 2, 3, 4, 5, 6, 7

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main
{
  public static void main(String[] args)
  {
    Member memberOne = new Member(1);
    Member memberTwo = new Member(2);
    Member memberThree = new Member(3);
    Member memberFour = new Member(4);
    Member memberFive = new Member(5);
    Member memberSix = new Member(6);
    Member memberSeven = new Member(7);

    memberTwo.setChildren(Arrays.asList(memberThree, memberFour));
    memberFour.setChildren(Arrays.asList(memberFive, memberSix));

    List memberList = Arrays.asList(memberOne, memberTwo, memberSeven);
    List flatList = new ArrayList<>();
    List convertedList = convertToFlatList(memberList, flatList);
    System.out.println(convertedList);
  }

  private static List convertToFlatList(List memberList, List flatList)
  {
    for (Member member : memberList)
    {
      if (member.getChildren() != null)
      {
        convertToFlatList(member.getChildren(), flatList);
      }
      else
      {
        flatList.add(member);
      }
    }
    return flatList;
  }
}

class Member
{
  private List children;

  private int memberId;

  Member(int memberId)
  {
    this.memberId = memberId;
  }

  List getChildren()
  {
    return children;
  }

  void setChildren(List children)
  {
    this.children = children;
  }

  int getMemberId()
  {
    return memberId;
  }

  void setMemberId(int memberId)
  {
    this.memberId = memberId;
  }

  @Override
  public String toString()
  {
    return String.valueOf(this.memberId);
  }
}

user_2422776 · Answer

If a Member has children, you correctly add the children to the flattened list, but miss the Member itself. Just move the addition of the member outside of the else block add you should be fine:

private static List 
convertToFlatList(List memberList, List flatList)
{
    for (Member member : memberList)
    {
        // Always add the member to flatList
        flatList.add(memeber);

        // If it has children, add them toore
        if (member.getChildren() != null)
        {
            convertToFlatList(member.getChildren(), flatList);
        }
    }
    return flatList;
}

user_7424948 · Answer

If you use Java 8, just add this method to the Member class:

public Stream streamAll(){
    if(getChildren() == null){
        return Stream.of(this);
    }
    return Stream.concat(Stream.of(this), getChildren().stream().flatMap(Member::streamAll));
}

Alternatively, you can remove the null check if you always initialize children to an empty list :

public Stream streamAll(){
    return Stream.concat(Stream.of(this), getChildren().stream().flatMap(Member::streamAll));
}

Then to get the flat list:

List convertedList = memberList.stream()
                                       .flatMap(Member::streamAll)
                                       .collect(Collectors.toList());

user_9959152 · Answer

Do this by using java-8 flatMap and recursion

Change convertToFlatList method to take only one argument (i,e List)

If getChildren() is not null, then do the recursion or else return the current object

private static List convertToFlatList(List memberList)
  {
       return memberList.stream().flatMap(i->{
          if(Objects.nonNull(i.getChildren())) {
             return Stream.concat(Stream.of(i), convertToFlatList(i.getChildren()).stream());
          }
          return Stream.of(i);

      }).collect(Collectors.toList());

  }

Output :

[1, 2, 3, 4, 5, 6, 7]

user_635891 · Answer

Actually this is the problem of level/recursive order traversal of a tree. Here is detail of the problem and solutions:

https://en.wikipedia.org/wiki/Tree_traversal

By the way, this is traversal (Depth first-Pre order) of your problem:

static class Member {
  List children = new ArrayList<>();
  int id;
  boolean visit = false;
}
public List printList(Member member) {
  Stack stack =  new Stack<>();
  List list =  new ArrayList<>();
  stack.push(member);
  while(!stack.isEmpty()) {
    Member node = stack.pop();
    list.add(node);
    for(Member m: node.children) {
    stack.push(m);
    }
  }
  return list;
}

Convert hierarchical list to a flat list in java

4 Answers