Create depth stream on Tree structure

Question

So, I have a basic tree structure consisting of tree nodes linking to other tree nodes with parent and children references. I want to create a method that returns a Stream that streams either from a leaf node to root node or root to leaf. I have implemented this already but I'm looking for a solution where the minimal amount of objects are created. Preferably none. Here is my code:

  public class TreeNode<TNode> {

      private TNode iValue;

      private TreeNode<TNode> iParentNode = null;

      private List<TreeNode<TNode>> iChildren = new ArrayList<>();

      public TreeNode(TNode value) {
          this(value, null);
      }

      private TreeNode(TNode value, TreeNode<TNode> parentNode) {
          iValue = value;
          iParentNode = parentNode;
      }

      public Stream<TreeNode<TNode>> streamFromLeaf() {
          return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new LeafFirstIterator(this), Spliterator.SIZED),
            false);
      }

      public Stream<TreeNode<TNode>> streamFromRoot() {
          return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new RootFirstIterator(this), Spliterator.SIZED),
            false);
      }

      public TNode getValue() {
          return iValue;
      }

      public TreeNode<TNode> getParent() {
          return iParentNode;
      }

      public TreeNode<TNode> addChild(TNode childValue) {
          TreeNode<TNode> childNode = new TreeNode<TNode>(childValue, iNodeNameFunction, this);
          iChildren.add(childNode);
          return childNode;
      }

      public boolean isLeaf() {
          return iChildren.size() == 0;
      }

      public boolean isRoot() {
          return iParentNode == null;
      }

      public List<TreeNode<TNode>> getChildren() {
          return iChildren;
      }

      class LeafFirstIterator implements Iterator<TreeNode<TNode>> {

          private TreeNode<TNode> iNextNode;

          LeafFirstIterator(TreeNode<TNode> leafNode) {
              iNextNode = leafNode;
          }

          @Override
          public boolean hasNext() {
              return iNextNode != null;
          }

          @Override
          public TreeNode<TNode> next() {
              TreeNode<TNode> current = iNextNode;
              iNextNode = current.getParent();
              return current;
          }

      }

      class RootFirstIterator implements Iterator<TreeNode<TNode>> {

          private List<TreeNode<TNode>> iNodes = new ArrayList<>();

          private int iNextIndex;

          RootFirstIterator(TreeNode<TNode> leafNode) {
              TreeNode<TNode> currentNode = leafNode;
              while (currentNode != null) {
                  iNodes.add(currentNode);
                  currentNode = currentNode.getParent();
              }
              iNextIndex = iNodes.size() - 1;
           }

           @Override
           public boolean hasNext() {
               return iNextIndex >= 0;
           }

           @Override
           public TreeNode<TNode> next() {
               return iNodes.get(iNextIndex--);
           }

       }
   }

This works fine but my "problem" is, a lot of objects are create for each stream call.

• StreamSupport.stream creates new ReferencePipeline
• Spliterators.spliteratorUnknownSize creates new IteratorSpliterator
• I create my own Iterator implementation to pass to Spliterator
• RootFirstIterator creates new ArrayList

The streams are going to be used heavily so I want do avoid object creation as much as possible. Iterating the tree structure without streams is a simple matter. Right now I'm only using the map method of stream. I could just have a method that takes a Consumer, iterate the depth and call the consumer for each node, and no objects would be created, but I would loose all stream functionality. That would look something like this:

public void iterateUp(Consumer<TreeNode<TNode>> consumer) {
    doIterateUp(this, consumer);
}

public static <T> void doIterateUp(TreeNode<T> node, Consumer<TreeNode<T>> consumer) {
    if (node == null)
        return;
    consumer.accept(node);
    doIterateUp(node.getParent(), consumer);
}

and iterating down from root would be just as simple.

Any ideas on this? Am I going about this the wrong way? Should TreeNode implement or extend some interface/class instead? Let me know if anything is unclear.

Thanks!

Answer 1

Don't use a stream. Use your alternative, which has a name: the visitor pattern.

Streams aren't always the right approach, and this is a classic case for using the visitor pattern.

If you absolutely must have a stream, have your consumer either collect the nodes in a List then stream that, or wire up the consumer to the next() method of an Iterator (with some code to make it behave properly) and use StreamSupport to turn it into a stream.

Answer 2

I don’t share your performance concerns, however, there is room for simplification of your code which might address some of your concerns as a side-effect.

You made the common mistake of starting with an Iterator implementation, much likely because the Iterator interface old and well known. But implementing it is cumbersome and the fact that you don’t need to wrap an Iterator in a Spliterator if you just implement Spliterator directly, is only a neat side effect:

public Stream<TreeNode<TNode>> streamFromLeaf() {
    return StreamSupport.stream(new LeafFirstSpliterator<>(this), false);
}
static class LeafFirstSpliterator<TNode>
extends Spliterators.AbstractSpliterator<TreeNode<TNode>> {
    private TreeNode<TNode> iNextNode;
    LeafFirstSpliterator(TreeNode<TNode> leafNode) {
        super(100, ORDERED|NONNULL);
        iNextNode = leafNode;
    }
    public boolean tryAdvance(Consumer<? super TreeNode<TNode>> action) {
        if(iNextNode==null) return false;
        action.accept(iNextNode);
        iNextNode=iNextNode.getParent();
        return true;
    }
}

To me, the Spliterator implementation looks much cleaner, at least it’s nothing to be afraid of, and it might allow a faster stream traversal. You might consider overriding the forEachRemaining method as well as it’s straight-forward to implement.

For the stream from root to leaf, a temporary storage seems to be unavoidable, but if it is, don’t waste time with low level coding at all, just use the storage’s built-in streaming capability:

public Stream<TreeNode<TNode>> streamFromRoot() {
    ArrayDeque<TreeNode<TNode>> deque = new ArrayDeque<>();
    for(TreeNode<TNode> n = this; n != null; n = n.getParent())
        deque.addFirst(n);
    return deque.stream();
}