Java Stream collect all children

Question

I would like to write a Java 8 stream().collect function that return a List<T> containing all children and subchildren of a node within a hierarchical structure. For example TreeItem<T> getChildren() and all of the children's children and so on, reducing it to a single list.

By the way, here is my final solution as generic method. Very effective and very useful.

public static <T> Stream<T> treeStream(T root, boolean includeRoot, Function<T, Stream<? extends T>> nextChildren)
{
    Stream<T> stream = nextChildren.apply(root).flatMap(child -> treeStream(child, true, nextChildren));
    return includeRoot ? Stream.concat(Stream.ofNullable(root), stream) : stream;
}

Can you share your `TreeItem` class please (or, at least, its relevant methods)? — Mureinik, Jul 08 '16 at 11:59
@Mureinik "My" TreeItem class is javafx.scene.control.TreeItem. Relevant method is getChildren(). — Arceus, Jul 08 '16 at 20:15

score 0 · Answer 1 · answered Jul 11 '16 at 15:07

0

You have to flatten the tree using a recursive function. You have an example here: http://squirrel.pl/blog/2015/03/04/walking-recursive-data-structures-using-java-8-streams/

answered Jul 11 '16 at 15:07

cdelmas

840
8
15

That's okay, but recursion is generally a bad idea since the stack could potentially become overflowed. – Arceus Jul 12 '16 at 19:10
If the tree is very deep, you can use [trampolines](https://github.com/aol/cyclops/wiki/trampoline-:-stackless-recursion-for-java-8) — here is a good [article in french](https://www.infoq.com/fr/articles/trampoline-java8) to avoid stack overflows: the code becomes less readable though. – cdelmas Jul 13 '16 at 08:25
Trampolines... I didn't know them, interesting. – Arceus Jul 13 '16 at 17:28

score 0 · Answer 2 · answered Jul 24 '16 at 23:26

In order not to fall with stack overflow there is a way to replace stack with queue in heap.

This solution creates stream from iterator that lazily navigates tree holding next items in Queue.

Depending on type of queue traversal can be depth first or breadth first

class TreeItem {
    Collection<TreeItem> children = new ArrayList<>();
}

Stream<TreeItem> flatten(TreeItem root) {
    Iterator<TreeItem> iterator = new Iterator<TreeItem>() {
        Queue<TreeItem> queue = new LinkedList<>(Collections.singleton(root)); //breadth first
//      Queue<TreeItem> queue = Collections.asLifoQueue(new LinkedList<>(Collections.singleton(root))); //depth first

        @Override public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override public TreeItem next() {
            TreeItem next = queue.poll();
            queue.addAll(next.children);
            return next;
        }
    };
    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false);
}

Java Stream collect all children

2 Answers2