Java: Turning a tree into a stream

Question

One of the advantages of streams is that you can avoid visiting the whole structure for some operations, like anyMatch or filter+findFirst. However, if you have your own data structure, depending on how you turn it into a stream you may end up visiting it all anyway. What is the right way to turn a custom tree data type into a stream? Consider the following example:

interface Tree{
  void forEach(Consumer<Integer> c);
}

final class EmptyTree implements Tree{
  public void forEach(Consumer<Integer> c){}
}

interface NonEmptyTree extends Tree{}

record Leave(int label) implements NonEmptyTree{
  public void forEach(Consumer<Integer> c){ 
    System.out.println("In forEachLeave "+label);
    c.accept(label);
    }
}

record Node(NonEmptyTree left, NonEmptyTree right) implements NonEmptyTree{
  public void forEach(Consumer<Integer> c){ 
    left.forEach(c); right.forEach(c);
  }
}

The two main ways to turn a tree into a stream would be

var sb=Stream.<Integer>builder();
myTree.forEach(sb);
sb.build()

or

Stream.of(myTree).mapMulti(Tree::forEach)

However, both of them call forEach, thus both of them will visit all the tree (and call the prints for all the labels, in this example).

How do you implement a .stream() method in the Tree type so that it would not even visit the whole tree if it is not needed? (because of .anyMatch, for example)

Answer 1

Ok, I sorted it. I'm quite sure that what I'm doing is pretty standard with immutable trees (parent fields only make sense in mutable trees)

Here is my result, for reference for future programmers doing streams on immutable trees. The class TreeIterator<E> is the one really relevant to this ordeal. I could make nested classes to be able to make more stuff private, but as a code example I think it is more clear in this non nested form.

interface Tree<E> extends Iterable<E>{
  
  Tree<E> and(Tree<E> other);
  
  default Tree<E> left(){ return empty(); }
  
  default Tree<E> right(){ return empty(); }
  
  default E label(Supplier<E> orElse){ return orElse.get(); }

  @SuppressWarnings("unchecked")
  static <E> Tree<E> empty(){ return (Tree<E>)EmptyTree.empty; }
  
  static <E> Tree<E> leaf(E label){ return new Leaf<E>(label); }

  default Stream<E> stream(){ return StreamSupport.stream(spliterator(), false); }
}

final class EmptyTree<E> implements Tree<E>{
  public Tree<E> and(Tree<E> other){ return other; }
  
  private EmptyTree(){} //Singleton pattern: only one EmptyTree can exists
  static final Tree<?> empty = new EmptyTree<>();
  
  public Iterator<E> iterator(){ return List.<E>of().iterator(); }

  public String toString(){ return "<EMPTY>"; }
}

interface NonEmptyTree<E> extends Tree<E>{
  
  Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack);
  
  default Tree<E> and(Tree<E> other){
    if (!(other instanceof NonEmptyTree<E> net)){ return this; }
    return new Node<E>(this, net);
  }
}
record Leaf<E>(E label) implements NonEmptyTree<E>{
  
  public E label(Supplier<E> orElse){ return label; }
  
  public Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack){ return this; }
  
  public Iterator<E> iterator(){ return List.<E>of(label).iterator(); }

  public String toString(){ return label+""; }
}

record Node<E>(NonEmptyTree<E> left, NonEmptyTree<E> right) implements NonEmptyTree<E>{

  public Node{ assert left!=null && right!=null; }//null is not a valid tree
  
  public Leaf<E> itAdvance(ArrayList<NonEmptyTree<E>> stack){
    stack.add(right);
    return left.itAdvance(stack);
    }

  public Iterator<E> iterator(){ return new TreeIterator<E>(this); }
  
  public String toString(){ return "("+left+", "+right+")"; }
  
}
class TreeIterator<E> implements Iterator<E>{
  
  private final ArrayList<NonEmptyTree<E>> stack = new ArrayList<>(32);
  
  public boolean hasNext(){ return !stack.isEmpty(); }
    
  public TreeIterator(Node<E> n){ stack.add(n); }
  
  public E next(){
    if(stack.isEmpty()){ throw new NoSuchElementException(); }
    var last=stack.remove(stack.size()-1);
    return last.itAdvance(stack).label();
  }
}

Answer 2

Looking at record definition Leave(int label) implements NonEmptyTree, I have two questions:

1. Did you mean "leaf"?
2. A tree consists of nodes (either a leaf or an internal node), but a node or leaf do not implement a tree, i.e., they are not are specific type of a tree. Are you sure about your node/leaf/tree implementation?

I would recommend a simple implementation like this one here: https://www.baeldung.com/java-binary-tree

When it comes to stream, you have two options:

1. Implement your own Stream-enabled class (see discussion here)
2. Provide a method that returns a (specific) stream, e.g. filtered.

Keep in mind that there are many different trees out there, e.g. red–black tree, n-ary tree, AVL Tree, B-Tree ...