Traversal of Infinite Complete Binary Trees

In the last post, we looked at code to generate an infinitely large binary tree. In this post we will look at how to traverse it.

Breadth First VS Depth First

First of all, an Infinite Complete Binary Tree can’t be effectively traversed with a depth-first traversal. Wikipedia states it quite eloquently:

“A basic requirement for traversal is to visit every node. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depth-first traversal will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed if in-order or post-order will never visit any nodes, as it has not reached a leaf (and in fact never will). By contrast, a breadth-first (level-order) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor.”

So for an infinite complete binary tree, the breadth first traversal is really the most useful. Let’s examine some approaches to a breadth first traversal for our PointNode tree.

Using Lists

To mix it up a little bit, we’ll write the unit test first. Here is a small set of test data containing the values of a breadth first traversal of our binary tree going three levels deep.

List breadthFirst;
breadthFirst = Arrays.asList(new BigDecimal(0.5),
                             new BigDecimal(0.25),
                             new BigDecimal(0.75),
                             new BigDecimal(0.125),
                             new BigDecimal(0.375),
                             new BigDecimal(0.625),
                             new BigDecimal(0.875));

And the test method might look like this. We can use lambda expressions to accumulate each node in the traversal.

@Test
public void breadthFirstSimple() throws Exception {

    List traversal = new ArrayList<>();
    PointNode.UNIT_INSTANCE.breadthFirstSimple((n)-> traversal.add(n.getValue()), 3);

    assertEquals(breadthFirst, traversal);
}

As a first pass at this problem, I think the simplest approach involves using lists to express what you do when you visualize traversal of a tree in breadth-first order. Imagine we’re given an arbitrary level of a tree. Given a list of nodes at that level, visit each one in the list. Once done, construct a new list of the ordered children of each of those nodes, and pass that list into the same method recursively. Note that with this approach, the public method can send the root node to the recursive method as a singleton list. Importantly: This recursive method call will never return unless there is an exit criteria. In the sample here, we use the tree depth as the exit criteria.

public void breadthFirstSimple(Consumer visitor, int depth) {
    breadthFirstSimple(visitor, Arrays.asList(this), depth);
}

protected void breadthFirstSimple(Consumer visitor, List supplier, int depth) {

    if(depth <= 0) {
        return;
    }

    for(PointNode node : supplier) {
        visitor.accept(node);
    }

    List subTrees = new ArrayList<>();
    for(PointNode node : supplier) {
        subTrees.addAll(Arrays.asList(node.getLeftChild(), node.getRightChild()));
    }

    breadthFirstSimple(visitor, subTrees, depth-1);

}

Using Lambdas

With Java 8 we can use lambdas to implement the above idea in a functional style. The unit test will look the same.

@Test
public void breadthFirst() throws Exception {

    List traversal = new ArrayList<>();
    PointNode.UNIT_INSTANCE.breadthFirst((n)-> traversal.add(n.getValue()), 3);

    assertEquals(breadthFirst, traversal);
}

Similarly to the approach above, we pass in a list of nodes but this time in the form of a Stream instead of a List. The Stream can visit each node with Stream.peek(), map each node to a stream of that node’s children, and reduce those child streams into a new single stream. Once all of the original nodes have been visited, we are left with a Stream of all the child nodes in breadth-first order. This approach constructs the child data structure and passes it along recursively after visiting all of the original nodes like we did above. But this time the child Stream is constructed as we visit each node instead of after we have visited all nodes. Again, because this is recursive we need an exit criteria.

public void breadthFirst(Consumer visitor, int depth) {
    breadthFirst(visitor, Stream.builder().add(this).build(), depth);
}

protected void breadthFirst(Consumer visitor, Stream supplier, int depth) {

    if(depth == 0) {
        return;
    }

    // want to accumulate child nodes into a stream
    Stream childStream = supplier.peek(visitor)
                                            .map((node) -> node.streamChildren())
                                            .reduce(Stream.empty(), Stream::concat);

    breadthFirst(visitor, childStream, depth - 1);
}

public Stream streamChildren() {
    return Stream.builder().add(this.getLeftChild()).add(this.getRightChild()).build().sequential();
}

Using Streams

The functional approach is nice, but suffers from a higher memory requirement, because nodes at each level are retained for each call in the stack. Also the caller needs to know how many levels deep it wants to go, requiring the caller to have knowledge of the tree structure to know how many nodes it can process. If we could return a Stream that iterates in breadth-first order, we would eliminate that requirement and allow for more Stream-oriented operations on the nodes we visit.

This is my favorite approach: a Stream whose elements are the ordered breadth-first traversal of the tree. This allows us to limit the number of returned elements directly and use the other useful methods on Stream. A test might look like this:

@Test
public void stream() throws Exception {

    List traversal = PointNode.UNIT_INSTANCE
            .stream()
            .map(n -> n.getValue())
            .limit(breadthFirst.size())
            .collect(Collectors.toList());

    assertEquals(breadthFirst, traversal);
}

To construct such a Stream, we need to implement a Spliterator (the iterator that backs up a Stream object). If you read the code below, you’ll notice that it takes the functional approach from above one step further. As it traverses each node in the stream, it does not build a new stream and reduce it into a stream of child nodes. Instead it bypasses the construction of a child stream and directly deposits the child nodes farther down in the current stream. The use of a Queue is very important in this case: we need to be able to deposit nodes farther down so that they will be encountered in order after all of the nodes at the current level have been visited in order.

This approach also uses less memory because it does not retain a reference to previously visited nodes.

public Stream stream() {
    return StreamSupport.stream(new BreadthFirstSpliterator(this), false);
}

protected static class BreadthFirstSpliterator extends AbstractSpliterator {

    private final Queue nodes = new LinkedBlockingQueue<>();

    public BreadthFirstSpliterator(PointNode root) {
        super(Long.MAX_VALUE, ORDERED | DISTINCT | NONNULL | IMMUTABLE);
        nodes.add(root);
    }

    @Override
    public boolean tryAdvance(Consumer action) {
        PointNode current = nodes.remove();
        action.accept(current);
        nodes.addAll(Arrays.asList(current.getLeftChild(), current.getRightChild()));
        return true;
    }
}

In the future we can cover other kinds of traversal, or other kinds of trees. Hopefully this has given you some insight into tree traversal!

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s