Binary Tree Iterators

In my last post, I presented code (and unit tests) for a binary tree implementation in Java. I alluded to the fact that there was a depth-first iterator in one of the test classes. This time I'll discuss iterators and present more practice code.

Iterator is one of the behavioral patterns described by the Gang of Four in their classic "Design Patterns". It provides the means for walking through a data structure without having to expose the details of how it's done.

Timothy Budd provides an excellent explanation of binary trees and iterators in chapter 10 of his "Classic Data Structures In C++".

Binary trees are interesting data structures. If the n nodes in a binary tree are independent, then there are n! = n*(n-1)*...*2*1 different orderings by which one could visit every node.

But the fact that the tree is arranged so that each parent has, at most, a left and right child limits the number of choices for walking the tree to six:

1. Process value, then left child, then right child
2. Process left child, then value, then right child
3. Process left child, then right child, then value
4. Process value, then right child, then left child
5. Process right child, then value, then left child
6. Process right child, then left child, then value

Subtrees are usually traversed from left to right, so the first three possibilities are the most common. Each is given a name that may be more familiar and memorable. The first is called preorder or depth-first traversal; the second in-order or symmetric traversal; and the third post-order traversal. There is also level order or breadth-first traversal, where all the nodes at one level are visited before proceeding to the next.

Java has an Iterator interface in its java.util package that defines the methods that all classes that implement it must provide. The next() returns a generic value. For my binary tree iterator I knew there'd be times when I wanted to get the next Node instead of the value, so I extended the Iterator interface and added a next method that returned a Node<T>:

package tree;

import java.util.Iterator;

public interface BinaryTreeIterator<T extends Comparable<T>> extends Iterator<T>
{
Node<T> nextNode();
}

Then I created an abstract class that provided default behavior for all methods except the ones that provided the next Node value and whether or not the walk through the tree was complete:

package tree;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import java.util.Iterator;

public abstract class AbstractBinaryTreeIterator<T extends Comparable<T>> implements BinaryTreeIterator<T>
{
public static final Log LOGGER = LogFactory.getLog(AbstractBinaryTreeIterator.class);

public void remove()
{
throw new UnsupportedOperationException("cannot remove from a binary tree");
}

public T next()
{
Node<T> nextNode = nextNode();

return nextNode.getValue();
}
}

The post-order traversal examines the left child first, then the right child, then the value in a recursive manner. It uses a last in, first out (LIFO) stack to hold the nodes in the opposite order they are to be visited. The iteration starts by pushing the root node onto the stack and recursing down the tree:

package tree;

import java.util.NoSuchElementException;
import java.util.Stack;

public class PostOrderIterator<T extends Comparable<T>> extends AbstractBinaryTreeIterator<T>
{
protected Stack<Node<T>> stack = new Stack<Node<T>>();

public PostOrderIterator(BinaryTree<T> tree)
{
init(tree.getRoot());
}

public void init(Node<T> root)
{
if (root != null)
{
stack.clear();
stackChildren(root);
}
}

private void stackChildren(Node<T> node)
{
stack.push(node);
Node<T> next = node.getRight();
if (next != null)
{
stackChildren(next);
}
next = node.getLeft();
if (next != null)
{
stackChildren(next);
}
}

public Node<T> nextNode()
{
if (!hasNext())
{
throw new NoSuchElementException();
}

Node<T> x = null;

if (!stack.empty())
{
if (LOGGER.isDebugEnabled())
{
LOGGER.debug(stack);
}

x = stack.pop();
}

return x;
}

public boolean hasNext()
{
return !stack.isEmpty();
}
}

Of course there are unit tests:

package tree;

import org.springframework.test.context.ContextConfiguration;
import static org.testng.Assert.assertFalse;
import static org.testng.AssertJUnit.assertEquals;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

@Test
@ContextConfiguration(locations = "classpath:app-context.xml, classpath:app-context-test.xml")
public class BinaryTreeIteratorTest
{
public void testHasNextEmptyTree()
{
BinaryTree<String> empty = new BinaryTree<String>();
AbstractBinaryTreeIterator<String> iterator = new DepthFirstIterator<String>(empty);

assertFalse(iterator.hasNext());
}

@Test(expectedExceptions = UnsupportedOperationException.class)
public void testRemove()
{
BinaryTree<String> empty = new BinaryTree<String>();
AbstractBinaryTreeIterator<String> iterator = new DepthFirstIterator<String>(empty);
iterator.remove();
}

public void testNextDepthFirst()
{
Integer[] data = {5, 3, 9, 1, 4, 6,};
BinaryTree<Integer> tree = new BinaryTree<Integer>();
tree.insert(data);

String expected = "5,3,1,4,9,6,";
AbstractBinaryTreeIterator<Integer> iterator = new DepthFirstIterator<Integer>(tree);
String actual = createCommaSeparatedString(iterator);

assertEquals(actual.toString(), expected);
}

public void testNextPostOrder()
{
Integer[] data = {5, 3, 9, 1, 4, 6,};
BinaryTree<Integer> tree = new BinaryTree<Integer>();
tree.insert(data);

String expected = "1,4,3,6,9,5,";
AbstractBinaryTreeIterator<Integer> iterator = new PostOrderIterator<Integer>(tree);
String actual = createCommaSeparatedString(iterator);

assertEquals(actual.toString(), expected);
}

private static String createCommaSeparatedString(Iterator iterator)
{
StringBuffer actual = new StringBuffer(1024);
while (iterator.hasNext())
{
actual.append(iterator.next()).append(',');
}

return actual.toString();
}

@DataProvider(name = "emptyTreeIterators")
public Object[][] createEmptyTreeIterators()
{
BinaryTree<String> tree = new BinaryTree<String>();

return new Object[][]{
{new BreadthFirstIterator<String>(tree)},
{new DepthFirstIterator<String>(tree)},
{new InOrderIterator<String>(tree)},
{new PostOrderIterator<String>(tree)},
};
}


@Test(expectedExceptions = NoSuchElementException.class, dataProvider = "emptyTreeIterators")
public void testNextEmptyTree(AbstractBinaryTreeIterator<String> iterator)
{
iterator.next();
}

public void testNext()
{
String[] data = {"F", "B", "A", "D", "C", "E", "G", "I", "H",};
BinaryTree<String> tree = new BinaryTree<String>();
tree.insert(data);

Map<String, String> expected = new HashMap<String, String>();
expected.put("depth-first", "F,B,A,D,C,E,G,I,H,");
expected.put("in-order", "A,B,C,D,E,F,G,H,I,");
expected.put("post-order", "A,C,E,D,B,H,I,G,F,");
expected.put("breadth-first", "F,B,G,A,D,I,C,E,H,");

String name = "depth-first";
AbstractBinaryTreeIterator<String> iterator = new DepthFirstIterator<String>(tree);
AbstractBinaryTreeIterator.LOGGER.debug(name);
assertEquals(name, expected.get(name), createCommaSeparatedString(iterator));

name = "in-order";
iterator = new InOrderIterator<String>(tree);
AbstractBinaryTreeIterator.LOGGER.debug(name);
assertEquals(name, expected.get(name), createCommaSeparatedString(iterator));

name = "post-order";
iterator = new PostOrderIterator<String>(tree);
AbstractBinaryTreeIterator.LOGGER.debug(name);
assertEquals(name, expected.get(name), createCommaSeparatedString(iterator));

name = "breadth-first";
iterator = new BreadthFirstIterator<String>(tree);
AbstractBinaryTreeIterator.LOGGER.debug(name);
assertEquals(name, expected.get(name), createCommaSeparatedString(iterator));
}
}

Tests are great, but being a visual person I like to be able to see a picture. There's a terrific package called graphviz from AT&T that lets you generate graph plots in an elegant way. I wrote a quick program to walk the binary tree { F,B,A,D,C,E,G,I,H } using an iterator and spit out the dot representation, like so:

digraph simple_hierarchy {
F->B [label="L"]
F->G [label="R"]
B->A [label="L"]
B->D [label="R"]
D->C [label="L"]
D->E [label="R"]
G->I [label="R"]
I->H [label="L"]
}

I can use this as the input to dot.exe to render the tree as .png or .svg file:



I'll post the other iterators next time.

All this work just to answer a single interview question! This tells me that doing it justice would be hard in such a short period of time. I would flunk such an interview.

Thanks to my friend Steve Roach, who was the first person to bring graphviz (and so many other things) to my attention. He's one of the most talented developers I've had the pleasure of working with, but it's his teaching ability that's his greatest strength. He's one of those people who makes everyone around him better. Such intellectual generosity is rare indeed.