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.

Practice, Practice, Practice

I spent several hours last week interviewing Java developers. We needed to bring in some contractors. It was decided that we'd ask candidates to write some Java code as part of the interview process. We had a list of twenty quiz questions that ranged in difficulty. Since our time was limited, we'd restrict ourselves to one or two quiz questions per candidate.

I had mixed feelings about the quiz questions. I'm familiar with Joel Spolsky's Guerrilla Guide to Interviewing. I didn't want to be a Quiz Show Interviewer.

But there was something else nagging me. How would I fare if presented with this quiz?

One of the questions was: "Traverse a binary tree in depth-first order." I'd bet that anybody fresh out of a good data structures class would be able to whip this out quickly enough to be able to fit into the scope of a 30 minute phone conversation.

But what about a guy like me?

The only data structure I was taught as a mechanical engineer was a FORTRAN array. I was keenly aware of my ignorance when I started down the software path, so I did what I always do: sign up for a degree and start taking courses. I started down the path of an Master of Science degree in computer science. It included basics like data structures, but they taught it using Eiffel. And that was ten years ago. I'd have to dredge up those memories and express them in Java.

Even worse, I've been working as an architect for years now. The big firms that employ me tend to take a dim view of architects that write code. Programming is considered a low level, commodity, low skill task that's best left to the least expensive off-shore individuals you can find.

It made me nervous to think about how foolish I'd look taking my own interview.

So I started working through the interview questions, one by one. I spent some time this weekend on that binary tree implementation. I got through it using all the best practices I knew: Java, test driven development using TestNG, IntelliJ and refactoring, etc. It took more than thirty minutes to finish, but I'm pleased with the result. I am not fast, but I think I'm conscientious and thorough.

Practice will help with my speed. Part of the value of this exercise is to practice, practice, practice. Individuals that I have a great deal of respect for advocate the concept of constant practice, calling it code kata.

I think it's especially important for someone with "architect" in their job title. How on earth can you represent for "best practices" when you're so woefully out of practice yourself?

The other benefit? It's fun and satisfying. There's still a great sense of satisfaction, of an aesthetic for mathematical beauty, whenever I manage to pull myself through whatever rabbit hole I've fallen into. There's frustration, too, when I struggle and fall and fail. But when it works, there's nothing like it.

It's no different from any other profession. We all have to keep learning, struggling, adding new skills, re-sharpening old ones.

If you're not a programmer, you can stop reading here. (Thank you for coming at all and getting this far.)

If you are a programmer, and you're still interested, here's my solution to the first part of the problem: a binary tree in Java. I started with a Node class that encapsulated a value plus left and right child references:

package tree;

public class Node<T extends Comparable<T>>
implements Comparable
{
private T value;
private Node<T> left;
private Node<T> right;

public Node(T value)
{
this(value, null, null);
}

public Node(T value, Node<T> left, 
Node<T> right)
{
this.setValue(value);
this.left = left;
this.right = right;
}

public T getValue()
{
return value;
}

public void setValue(T value)
{
if (value == null)
throw new IllegalArgumentException("node value 
cannot be null");

this.value = value;
}

public Node<T> getLeft()
{
return left;
}

public void setLeft(Node<T> left)
{
this.left = left;
}

public Node<T> getRight()
{
return right;
}

public void setRight(Node<T> right)
{
this.right = right;
}

public boolean isLeaf()
{
return ((this.left == null) && 
(this.right == null));
}

public int compareTo(Object o)
{
Node<T> other = (Node<T>) o;

return this.getValue().compareTo(other.getValue());
}

@Override
public boolean equals(Object o)
{
if (this == o)
{
return true;
}
if (o == null || getClass() != o.getClass())
{
return false;
}

Node node = (Node) o;

if (!value.equals(node.value))
{
return false;
}

return true;
}

@Override
public int hashCode()
{
return value.hashCode();
}

@Override
public String toString()
{
return value.toString();
}
}

Of course I wrote a TestNG class to unit test it:

package tree;

import static org.testng.Assert.*;
import org.testng.annotations.Test;

@Test
public class NodeTest
{
/**
* For any non-null reference value x, x.equals(null) 
* must return false.
*/
public void testNotNull()
{
Node<String> x 
= new Node<String>("test");

assertFalse(x.equals(null));
}

/**
* It is reflexive: For any reference value x, 
* x.equals(x) must return true.
*/
public void testReflexive()
{
Node<String> x 
= new Node<String>("test");

assertTrue(x.equals(x));
assertEquals(0, x.compareTo(x));
}

/**
* It is symmetric: For any reference values x and y, 
* x.equals(y) must return
* true if and only if y.equals(x) returns true.
*/
public void testSymmetric()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("something else");

assertTrue(x.equals(y) && y.equals(x));
assertTrue((x.compareTo(y) == 0) 
&& (y.compareTo(x) == 0));
assertFalse(x.equals(z));
assertTrue(x.compareTo(z) > 0);
}

/**
* It is transitive: For any reference values x, y, 
* and z, if x.equals(y) returns
* true and y.equals(z) returns true, 
* then x.equals(z) must return true
*/
public void testTransitive()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("test");

assertTrue(x.equals(y) && 
y.equals(z) && 
z.equals(x));
assertTrue((x.compareTo(y) == 0) && 
(y.compareTo(z) == 0) && 
(z.compareTo(x) == 0));
}

public void testHashCode()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("something else");

assertTrue(x.hashCode() == y.hashCode());
assertFalse(x.hashCode() == z.hashCode());
}

public void testToString()
{
String expected = "expected";

Node<String> node 
= new Node<String>(expected);
assertEquals(node.toString(), expected);
}

@Test(expectedExceptions = NullPointerException.class)
public void testCompareToNull()
{
Node<String> x 
= new Node<String>("test");

x.compareTo(null);
}

public void testCompareTo()
{
Node<String> x 
= new Node<String>("x");
Node<String> y 
= new Node<String>("y");
Node<String> z 
= new Node<String>("z");

assertTrue((x.compareTo(x) == 0) && 
(x.compareTo(y) <  0) && 
(x.compareTo(z) <  0));
assertTrue((y.compareTo(x) >  0) && 
(y.compareTo(y) == 0) && 
(y.compareTo(z) <  0));
assertTrue((z.compareTo(x) >  0) && 
(z.compareTo(y) >  0) && 
(z.compareTo(z) == 0));
}

@Test(expectedExceptions = IllegalArgumentException.class)
public void testNullValue()
{
Node<String> x   
= new Node<String>(null);
}

public void testIsLeaf()
{
Node<String> x 
= new Node<String>("test");

assertTrue(x.isLeaf());

x.setLeft(new Node<String>("left"));
x.setRight(new Node<String>("right"));

assertFalse(x.isLeaf());

assertEquals("left", x.getLeft().getValue());
assertEquals("right", x.getRight().getValue());
}
}

Then I wrote a BinaryTree:

package tree;

import java.util.Arrays;
import java.util.List;

public class BinaryTree<T 
extends Comparable<T>>
{
private Node<T> root;

public BinaryTree()
{
this(null);
}

public BinaryTree(Node<T> root)
{
this.root = root;
}

public Node<T> getRoot()
{
return this.root;
}

public boolean contains(T value)
{
return contains(this.root, value);
}

private boolean contains(Node<T> node, T value)
{
// empty tree can't contain the value; value 
// cannot be null
if ((node == null) || (value == null))
{
return false;
}

if (value.equals(node.getValue()))
{
return true;
}
else if (value.compareTo(node.getValue()) < 0)
{
return contains(node.getLeft(), value);
}
else
{
return contains(node.getRight(), value);
}
}

public void insert(T value)
{
this.root = insert(this.root, value);
}

public void insert(List<T> values)
{
if ((values != null) && 
(values.size() > 0))
{
for (T value : values)
{
insert(value);     
}
}
}

public void insert(T [] values)
{
if ((values != null) && 
(values.length > 0))
{
insert(Arrays.asList(values));
}
}
private Node<T> insert(Node<T> node, 
T value)
{
if (node == null)
{
return new Node<T>(value);
}
else
{
if (value.compareTo(node.getValue()) < 0)
{
node.setLeft(insert(node.getLeft(), value));
}
else
{
node.setRight(insert(node.getRight(), value));           
}
}

return node;
}

public int size()
{
return size(root);
}

private int size(Node<T> node)
{
if (node == null)
{
return 0;
}
else
{
return (size(node.getLeft()) + 
1 + 
size(node.getRight()));
}
}

public int height()
{
return height(root);
}

private int height(Node<T> node)
{
if (node == null)
{
return 0;
}
else
{
int leftHeight = height(node.getLeft());
int rightHeight = height(node.getRight());

return (Math.max(leftHeight, rightHeight) + 1);
}
}

public boolean isEmpty()
{
return (root == null);
}
}

And a TestNG unit test:

package tree;

import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import static org.testng.AssertJUnit.assertEquals;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.Test;

import java.util.Arrays;
import java.util.List;

@Test
public class BinaryTreeTest
{
private BinaryTree<Integer> tree;
private Integer [] data = { 5, 3, 9, 1, 4, 6, };

@BeforeTest
public void setUp()
{
tree = new BinaryTree<Integer>();
tree.insert(data);
}

public void testIsEmpty()
{
assertFalse(tree.isEmpty());
assertTrue(new BinaryTree<Integer>().isEmpty());
}

public void testSize()
{
assertEquals(tree.size(), data.length);
}

public void testHeight()
{
int expected = 3;
assertEquals(tree.height(), expected);
}

public void testGetRoot()
{
Node<Integer> expected 
= new Node<Integer>(data[0]);
assertEquals(tree.getRoot(), expected);
}

public void testContains()
{
for (int value : data)
{
assertTrue(tree.contains(value));
assertFalse(tree.contains(value*1000));
}
}

public void testInsertList()
{
// When you insert a list, you get it back without 
// alteration using a pre-order, depth-first traversal.
List<String> data 
= Arrays.asList("F","B","A","D","C","E","G","I","H");
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

// Check the size
assertEquals(tree.size(), data.size());

// Now check the values
BinaryTreeIterator<String> iterator 
= new DepthFirstIterator<String>(tree);
int i = 0;
while (iterator.hasNext())
{
assertEquals("i = " + i, iterator.next(), 
data.get(i++));
}
}

public void testInsertArray()
{
// When you insert a list, you get it back without 
// alteration using a pre-order, depth-first traversal.
String [] data = {"F","B","A","D","C","E","G","I","H",};
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), data.length);     

BinaryTreeIterator<String> iterator 
= new DepthFirstIterator<String>(tree);
int i = 0;
while (iterator.hasNext())
{
assertEquals("i = " + i, iterator.next(), 
data[i++]);     
}
}

public void testInsertNullList()
{
List<String> data = null;
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), 0);
}

public void testInsertNullArray()
{
String [] data = null;
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), 0);
}
}

This was the ground work. The real solution meant writing iterators to traverse the BinaryTree. If you're reading closely, you'll see that I used a DepthFirstIterator in the unit test for BinaryTree.

I'll post those next time. In the meantime, I'll keep practicing.