Unit test proper data structure creation

Question

How would one test whether data structure built properly? I'm implementing kind of modified radix tree, and been wondering how do you check if your data structure builds up correctly.

Consider a tree of TreeNode {String, Int} nodes. You always want to append new child to deepest node of value equal to 0, as in following example:

Root, 0
- Child_1, 5
- Child_2, 0
   - Child_3, 1

Question is, how to unit test if tree structure builds up as you wished? TreeNode only has one method, which would be insert.

My idea so far was to write TreeVisitor that would walk through tree and convert each node to string. Tree from example above, could look like this:

[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]

Knowing algorithm that builds tree, I can create such string manually if I have idea what elements I'm inserting. My unit test would look like this (using same example).

TreeNode root = new TreeNode("Root", 0);
root.insert(new TreeNode("Child_1", 5));
root.insert(new TreeNode("Child_2", 0));
root.insert(new TreeNode("Child_3", 1));
TreeVisitor visitor = new TreeVisitor();
String expected = "[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]";
asssertEquals(expected, visitor.visit(root));

I got the feeling it's not best approach. To start of, as soon as visitor changes, all tests will fail (simply put change [ ] to ( )). Also, this approach allows me to test pretty small trees (as big as I can compute manually). How would you test bigger ones?

General question is, how to write tests checking whether data structure builds up correctly?

I assume I might be getting whole testing idea wrong, as I'm fresh from dozen tutorials where people test whether .Sum(a, b) works as expected :-)

Answer 1

This is looks like a case of Test Driven Design in action. An interface with only an 'insert' method is untestable, because it is also unusable. Building a tree, without being able to see, or do anything with, the tree you have built doesn't get you anywhere.

Work out how you want clients to access the tree (access methods, visitor interface, or whatever). Then test it through them.

If there is internal complexity you can't easily get at through the public interface (i.e. the tree is more like a Java TreeMap than the type of tree you put in a TreeView), you can use:

• assertions and invariants
• something like an exposed debugVerifyTree method.
• brute force: insert 36542 pseudo-random items, use a coverage tool to check that covers all cases.

Whichever way, any time you write a test, make sure you ask the question 'will any client of this code care if this test fails?'. If not, delete it.

Answer 2

Perhaps you can replace the implementation of TreeNode in the unit test with your own subclass that exposes methods to let you inspect the current set of children recursively. These methods would be additions to the TreeNode implementation to aid unit testing and wouldn't replace its existing functionality, so you'd still have a valid test.

Answer 3

What I usually end up doing is making the values or names indicative of the thing you are testing for. So in the case of a tree, the name might indicate the depth and the child index.

TreeNode root = new MyTreeNode("0.0", 0);
root.insert(new MyTreeNode("1.0", 5));
root.insert(new MyTreeNode("1.1", 0));
root.insert(new MyTreeNode("2.0", 1));
verify(root, 0, 0);
...
public void verify(TreeNode node, int depth, int index) {
   verifyName(node, depth, index);
   int numChildren = node.getChildCount();
   depth++;
   for (int i = 0; i < numChildren; i++) {
      verify(node.getChildAt(i), depth, i);
   }
}
public void verifyName(TreeNode node, int depth, int index) {
   StringBuilder expectedName = new StringBuilder();
   expectedName.append(depth).append('.').append(index);
   assertEquals("Tree node not in expected place",
                expectedName.toString(), node.getName());
}

Now I could imagine testing a fairly large tree. If the depth of the recursion is a problem, then you could unwrap the recursive method with the use of a stack instead.

public void verify(TreeNode root) {
   Stack<TreeNode> toBeVerified = new Stack<TreeNode>();
   verifyName(root, 0, 0);
   toBeVerified.push(root);

   while(!toBeVerified.isEmpty()) {
     TreeNode node = toBeVerified.pop();
     int depth = getDepth(node.getName()) + 1;
     int numChildren = node.getChildCount();
     for (int i = 0; i < numChildren; i++) {
        verifyName(node, depth, i);
        toBeVerified.push(node);
     }
   }
}
public int getDepth(String name) {
   return Integer.parseInt(name.substring(0, name.indexOf('.')));
}