Package com.google.mu.util.graph

Class BinaryTreeWalker<N>

java.lang.Object
com.google.mu.util.graph.Walker<N>
com.google.mu.util.graph.BinaryTreeWalker<N>
Type Parameters:
N - the tree node type
public final class BinaryTreeWalker<N> extends Walker<N>
Walker for binary tree topology (see Walker.inBinaryTree()).

Besides pre-order, post-order and breadth-first traversals, also supports in-order.

Since:
4.2

  • Method Details

    • breadthFirstFrom

      public Stream<N> breadthFirstFrom(Iterable<? extends N> roots)
      Returns a lazy stream for breadth-first traversal from root. Empty stream is returned if roots is empty.
      Specified by:
      breadthFirstFrom in class Walker<N>

    • preOrderFrom

      public Stream<N> preOrderFrom(Iterable<? extends N> roots)
      Returns a lazy stream for pre-order traversal from roots. Empty stream is returned if roots is empty.
      Specified by:
      preOrderFrom in class Walker<N>

    • postOrderFrom

      public Stream<N> postOrderFrom(Iterable<? extends N> roots)
      Returns a lazy stream for post-order traversal from root. Empty stream is returned if roots is empty.

      For small or medium sized in-memory trees, it's equivalent and more efficient to first collect the nodes into a list in "reverse post order", and then use Collections.reverse(), as in: 

      
   List<Node> nodes =
       Walker.inBinaryTree(Tree::right, Tree::left)    // 1. flip left to right
           .preOrderFrom(root)                         // 2. pre-order
           .collect(toCollection(ArrayList::new));     // 3. in reverse-post-order
   Collections.reverse(nodes);                         // 4. reverse to get post-order
      Or, use the toListAndThen() collector to do it in one-liner: 
      
   List<Node> nodes =
       Walker.inBinaryTree(Tree::right, Tree::left)
           .preOrderFrom(root)
           .collect(toListAndThen(Collections::reverse));
      Specified by:
      postOrderFrom in class Walker<N>

    • inOrderFrom

      @SafeVarargs public final Stream<N> inOrderFrom(N... roots)
      Returns a lazy stream for in-order traversal from roots. Empty stream is returned if roots is empty.

    • inOrderFrom

      public Stream<N> inOrderFrom(Iterable<? extends N> roots)
      Returns a lazy stream for in-order traversal from roots. Empty stream is returned if roots is empty.