How to recursively flatMap a stream?

Question

I was asked to retrieve every leaf node that is a descandant of a tree node. I quickly got the idea that I could do this job in one line!

public Set<TreeNode<E>> getLeaves() {
    return getChildrenStream().flatMap(n -> n.getChildrenStream()).collect(toSet());
}

It was good at the first glance, but quickly it ran into a StackOverflowExcepetionif the tree depth reaches ~10, something that I can't accept. Later I developed a implementation without recursion and stream (but with my brain roasted), but I'm still wondering if there is a way to do recursive flatMaps with stream, because I found it impossible to do so without touching the stream internals. It'll need a new Op, like RecursiveOps to do that, or I will have to collect all results into a Set every step, and operate on that Set later:

Set<TreeNode<E>> prev = new HashSet<>();
prev.add(this);
while (!prev.isEmpty()) {
    prev = prev.stream().flatMap(n -> n.getChildrenStream()).collect(toSet());
}
return prev;

Not good as it seems to be. Streams are meant to be a pipeline. Its result and intermediate results are not computed until a terminal op is added. The above approach appearently violates that principle. It's not as easy to parellelize as streams, too. Can I recursively flatMap without manually computing all intermediate results?

PS1: the TreeNode declaration:

public class TreeNode<E> {
    // ...
    /**
     * Get a stream of children of the current node. 
     *
     */
    public Stream<TreeNode<E>> getChildrenStream(){
        // ...
    }

    public Set<TreeNode<E>> getLeaves() {
        // main concern
    }
}f

This looks very related to this other question http://stackoverflow.com/questions/32749148/in-java-how-do-i-efficiently-and-elegantly-stream-a-tree-nodes-descendants. Does it answer your question? (it is not a simple problem) — Tunaki, May 28 '16 at 13:39
@Tunaki thanks that's what i'm looking for. didn't search with that keyword, though. — glee8e, May 29 '16 at 10:24

Joao Esperancinha · Answer 1 · 2016-05-28T15:49:50.257

Not entirely sure if this would be something that you would be interested in:

public static Set<TreeNode<String>> getAllLeaves(TreeNode<String> treeNode) {
    final Stream<TreeNode<String>> childrenStream = treeNode.getChildrenStream();
    if (childrenStream == null) {
        return new HashSet<>();
    }

    Set<TreeNode<String>> ownLeaves = treeNode.getLeaves();
    ownLeaves.addAll(childrenStream.flatMap(stringTreeNode -> getAllLeaves(stringTreeNode).parallelStream())
            .collect(Collectors.toSet()));

    return ownLeaves;
}

Out of the box I see a few inconvenients with this method. It does return an empty Set for the last iteration and It's creating streams as it does the flatMap. However I believe this is what you are looking for, since you are thinking about using flatMap from where you want to get a joined Set created recursively where no stream was created in the first place. Btw, I've tried this with a -1000 level and it still works quite fast and with no problem.

How to recursively flatMap a stream?

1 Answers1