CODEWITHSUNDEEP
javalistrecursion
Sandeepa
Sandeepa

Reputation: 3755

Convert hierarchical list to a flat list in java

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<Member> memberList = Arrays.asList(memberOne, memberTwo, memberSeven);
    List<Member> flatList = new ArrayList<>();
    List<Member> convertedList = convertToFlatList(memberList, flatList);
    System.out.println(convertedList);
  }

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

class Member
{
  private List<Member> children;

  private int memberId;

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

  List<Member> getChildren()
  {
    return children;
  }

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

  int getMemberId()
  {
    return memberId;
  }

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

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

Upvotes: 4

Views: 3009

Answers (4)

Ryuzaki L
Ryuzaki L

Reputation: 40058

Do this by using java-8 flatMap and recursion

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

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

private static List<Member> convertToFlatList(List<Member> 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]

Upvotes: 2

Mostafa Barmshory
Mostafa Barmshory

Reputation: 2039

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<Member> children = new ArrayList<>();
  int id;
  boolean visit = false;
}
public List<Member> printList(Member member) {
  Stack<Member> stack =  new Stack<>();
  List<Member> 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;
}

Upvotes: 1

Ricola
Ricola

Reputation: 2922

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

public Stream<Member> 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<Member> streamAll(){
    return Stream.concat(Stream.of(this), getChildren().stream().flatMap(Member::streamAll));
}

Then to get the flat list:

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

Upvotes: 9

Mureinik
Mureinik

Reputation: 311348

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<Member> 
convertToFlatList(List<Member> memberList, List<Member> 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;
}

Upvotes: 8

Related Questions