Traversal.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.function.Supplier;
import java.util.stream.Stream;

public interface Traversal<T> {
  enum Order {
    DEEP_FIRST {
      @Override
      <T> Stream<T> traverse(T node, Traversal<T> traversal, int depth) {
        return (depth == 0)?
          Stream.of(node):
          Stream.concat(Stream.of(node), traversal.stream(node).flatMap(child -> traverse(child, traversal, depth - 1)));
      }
    },
    BREATH_FIRST {
      @Override
      <T> Stream<T> traverse(T root, Traversal<T> traversal, int depth) {
        ArrayDeque<Supplier<T>> queue = new ArrayDeque<>();
        queue.offer(work(root, traversal, depth, queue));
        return Stream.iterate((Supplier<T>)() -> null, child -> child != null, __ -> queue.poll())
          .skip(1)
          .map(Supplier::get);
      }
      
      // look ma ! you do not need tuples
      private <T> Supplier<T> work(T node, Traversal<T> traversal, int depth, ArrayDeque<Supplier<T>> queue) {
        return () -> {
          traversal.stream(node)
            .filter(__ -> depth != 0)
            .forEach(child -> queue.offer(work(child, traversal, depth - 1, queue)));
          return node;
        };
      }
    };
    
    abstract <T> Stream<T> traverse(T node, Traversal<T> traversal, int maxDepth);
  }
  
  Stream<T> stream(T node);
  
  default Stream<T> traverse(T root, Order order) {
    return traverse(root, order, Integer.MAX_VALUE);
  }
  default Stream<T> traverse(T root, Order order, int maxDepth) {
    return order.traverse(root, this, maxDepth);
  }
  
  static <T> Traversal<T> of(Traversal<T> traversal) { return traversal; }
  
  
  // - example -
  
  public static class Tree {
    private final int value;
    final ArrayList<Tree> children = new ArrayList<>();

    public Tree(int value) { this.value = value; } 
    public Stream<Tree> children() { return children.stream(); }
    @Override
    public String toString() { return "" + value; }
  }
  
  public static void main(String[] args) {
    Tree root = new Tree(0);
    Tree subtree = new Tree(2);
    Collections.addAll(subtree.children, new Tree(3), new Tree(4));
    Collections.addAll(root.children, new Tree(1), subtree, new Tree(5));
    
    //of(Tree::children)
    //  .traverse(root, Order.DEEP_FIRST).map(Object::toString).forEach(System.out::println);
    of(Tree::children)
    .traverse(root, Order.BREATH_FIRST).map(Object::toString).forEach(System.out::println);
  }
}