How can I get all leaves elements of a recursive nested structure Data?

public class Item {
    private String id;
    private List<Item> items;
}

Exemple:

    A
      - AA
        - aa1
      - AB
        - ab1
          - abab1 
      - a1

Result

In the result I need to get only the following list of elements [aa1, abab1, a1]

CodePudding user response：

You can do it quite easily in a recursive fashion:

public static List<Item> findLeaves(Item rootItem){
    List<Item> leaves = new ArrayList<>();
    recursivelyCollectLeaves(leaves, rootItem);
    return leaves;
}

private static void recursivelyCollectLeaves(List<Item> leaves, Item actualItem){
    if(actualItem.getItems().isEmpty()){
        //No children, the actual item is a leaf
        leaves.add(actualItem);
    }
    else{
        for(Item child : actualItem.getItems()){
            recursivelyCollectLeaves(leaves, child);
        }
    }
}

PS: In order to make this code work, please note that I added getters to the Item class.

CodePudding user response：

How about adapting Item like this:

public static class Item {
    private final String id;
    private final List<Item> items;

    public Stream<Item> getLeaves() {
        if (items == null || items.isEmpty()) {
            return Stream.of(this);
        }
        return items.stream()
            .flatMap(Item::getLeaves);
    }

}

Which you can then use as:

final var item = new Item(
    "A",
    List.of(
        new Item("AA",
            List.of(new Item("aa1"))
        ),
        new Item("AB",
            List.of(new Item("ab1",
                List.of(new Item("abab1")))
            )
        ),
        new Item("a1")
    )
);

final var leaves = item.getLeaves()
    .map(Item::getId)
    .collect(Collectors.toList());

System.out.println(leaves);

Note: constructors and getters omitted for brevity

CodePudding user response：

Try adding this method to the class:

public List<Item> getLeaves() {
    ArrayList<Item> list = new ArrayList<>();
    if (items.size() == 0) {
        list.add(this);
    } else {
        for (Item item : items) {
            list.addAll(item.getLeaves());
        }
    }
    return list;
}

It just checks if itself is a leaf. If it is, it returns itself, if not, it returns all of the leaves of its children.