How to convert a tree structure to a Stream of nodes in java

Question

I want to convert a tree in a Java8 stream of nodes.

Here is a tree of nodes storing data which can be selected:

public class SelectTree<D> {

  private D data;

  private boolean selected = false;

  private SelectTree<D> parent;

  private final List<SelectTree<D>> children = new ArrayList<>();

  public SelectTree(D data, SelectTree<D> parent) {
    this.data = data;
    if (parent != null) {
      this.parent = parent;
      this.parent.getChildren().add(this);
    }
  }

  public D getData() {
    return data;
  }

  public void setData(D data) {
    this.data = data;
  }

  public boolean isSelected() {
    return selected;
  }

  public void setSelected(boolean selected) {
    this.selected = selected;
  }

  public SelectTree<D> getParent() {
    return parent;
  }

  public void setParent(SelectTree<D> parent) {
    this.parent = parent;
  }

  public List<SelectTree<D>> getChildren() {
    return children;
  }

  public boolean isRoot() {
    return this.getParent() == null;
  }

  public boolean isLeaf() {
    return this.getChildren() == null || this.getChildren().isEmpty();
  }
}

I want to get a collection of the selected data

I want to do something like that:

  public static void main(String[] args) {
    SelectTree<Integer> root = generateTree();
    
    List<Integer> selectedData = root.stream()
            .peek(node -> System.out.println(node.getData()+": "+node.isSelected()))
            .filter(node-> node.isSelected())
            .map(node-> node.getData())
            .collect(Collectors.toList()) ;
    
    System.out.println("\nselectedData="+selectedData);
  }

  private static SelectTree<Integer> generateTree() {
    SelectTree<Integer> n1 = new SelectTree(1, null);
    SelectTree<Integer> n11 = new SelectTree(11, n1);
    SelectTree<Integer> n12 = new SelectTree(12, n1);
    n12.setSelected(true);
    SelectTree<Integer> n111 = new SelectTree(111, n11);
    n111.setSelected(true);
    SelectTree<Integer> n112 = new SelectTree(112, n11);
    SelectTree<Integer> n121 = new SelectTree(121, n12);
    SelectTree<Integer> n122 = new SelectTree(122, n12);
    return n1;
  }

The problem was to find the implementation of stream() and I think I could help some people sharing my solution and I would be interested in knowing if there are some issues or better ways of doing this.

At first it was for primefaces TreeNode but I generalize the problem to all kinds of trees.

Possible duplicate of [In Java, how do I efficiently and elegantly stream a tree node's descendants?](http://stackoverflow.com/questions/32749148/in-java-how-do-i-efficiently-and-elegantly-stream-a-tree-nodes-descendants) — Didier L, May 22 '17 at 08:48

score 16 · Answer 1 · answered May 27 '16 at 13:12

One small addition to kwisatz's answer.

This implementation:

this.getChildren().stream()
        .map(SelectTree::stream)
        .reduce(Stream.of(this), Stream::concat);

will be more eager, i. e. the whole hierarchy will be traversed during a stream creation. If your hirarchy is large and, let's say, you're looking for a single node matching some predicate, you may want a more lazy behaviour:

Stream.concat(Stream.of(this),
              this.getChildren().stream().flatMap(SelectTree::stream));

In this case, only the children of the root node will be retrieved during a stream creation, and a search for a node won't necessarily result in the whole hierarchy being traversed.

Both approaches will exhibit the DFS iteration order.

Even [the documentation](https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#concat-java.util.stream.Stream-java.util.stream.Stream-) warns about overusing `concat`: “*Use caution when constructing streams from repeated concatenation. Accessing an element of a deeply concatenated stream can result in deep call chains, or even StackOverflowException[sic].*” So `reduce(Stream.of(this), Stream::concat)` should make the alarm bells ring. In Java 8, the `flatMap` approach isn’t as lazy as it should be, but at least, it’s not prone to stack overflows. In newer versions, it’s lazy. — Holger, Jan 27 '23 at 08:04

score 10 · Accepted Answer · edited Nov 06 '19 at 12:32

I find this implementation of stream() which is a DFS tree traversal:

public class SelectTree<D> {

  //...

  public Stream<SelectTree<D>> stream() {
    if (this.isLeaf()) {
      return Stream.of(this);
    } else {
      return this.getChildren().stream()
                .map(child -> child.stream())
                .reduce(Stream.of(this), (s1, s2) -> Stream.concat(s1, s2));
    }
  }
}

If you can't change the tree implementation like for primefaces TreeNode (org.primefaces.model.TreeNode) you can define a method in an other class:

  public Stream<TreeNode> stream(TreeNode parentNode) {
    if(parentNode.isLeaf()) {
      return Stream.of(parentNode);
    } else {
      return parentNode.getChildren().stream()
                .map(childNode -> stream(childNode))
                .reduce(Stream.of(parentNode), (s1, s2) -> Stream.concat(s1, s2)) ;
    }
  }

score 3 · Answer 3 · edited Nov 01 '20 at 22:36

A more general approach using any node class is to add a parameter for the method, which returns the children:

public class TreeNodeStream {
  public static <T> Stream<T> of(T node, Function<T, Collection<? extends T>> childrenFunction) {
    return Stream.concat( //
      Stream.of(node), //
      childrenFunction.apply(node).stream().flatMap(n -> of(n, childrenFunction)));
  }
}

An example using File:

TreeNodeStream.of(
  new File("."), f -> f.isDirectory() ? Arrays.asList(f.listFiles()) :
                                        Collections.emptySet())
  .filter(f -> f.getName().endsWith(".java"))
  .collect(Collectors::toList);

How to convert a tree structure to a Stream of nodes in java

3 Answers3

Linked