Why am I getting an AssertionError when the expected and actual look identical?

Question

I'm trying to answer the following question from Cracking the Coding Interview. The code below is part of a project on GitHub, here.

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).

Being a good little developer, I wrote a unit test to check this.

@Test
public void testGetValuesAtEachLevel() {
    Integer[] treeValues = {
            1, 2, 3, 4, 5,
            6, 7, 8, 9, 10,
            11, 12, 13, 14, 15
    };

    tree = new GenericBinaryTree<>(treeValues);

    Integer[][] expectedArray = {
            { 1 },
            { 2, 3 },
            { 4, 5, 6, 7 },
            { 8, 9, 10, 11, 12, 13, 14, 15 }
    };

    List<List<Node<Integer>>> expectedList = new ArrayList<>(4);
    for (Integer[] level : expectedArray) {
        List<Node<Integer>> list = new LinkedList<>();
        for (Integer value : level) {
            list.add(new Node<>(value));
        }
        expectedList.add(list);
    }

    assertEquals(expectedList, tree.getValuesAtEachLevel());
}

And here's the code.

List<List<Node<T>>> getValuesAtEachLevel() {
    List<List<Node<T>>> results = new ArrayList<>();

    List<Node<T>> firstLevel = new LinkedList<>();
    firstLevel.add(getRoot());
    results.add(firstLevel);

    loadAtLevel(results, 1);

    return results;
}

private void loadAtLevel(List<List<Node<T>>> list, int level) {
    List<Node<T>> levelList = new LinkedList<Node<T>>();

    for (Node<T> node : list.get(level - 1)) {
        if (node.left() != null) levelList.add(node.left());
        if (node.right() != null) levelList.add(node.right());
    }

    if (levelList.isEmpty()) return;

    level++;
    list.add(levelList);
    loadAtLevel(list, level);
}

Imagine my surprise when the unit test fails with the following error:

java.lang.AssertionError: expected: 
java.util.ArrayList<[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]> but was: 
java.util.ArrayList<[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]>

The string representations are identical, so I can't really figure out what happened here. As a matter of fact, if I change the assertion to this, the test passes:

    assertEquals(expectedList.toString(), tree.getValuesAtEachLevel().toString());

I'm getting the sense I'm about to learn something awfully valuable about interfaces and objects. What did I do wrong here?

Solution 1

As pointed by @Jon Skeet in the comment as well, you need to override the equals and hashCode for your Node class, to perform a comparison (equals) on its instances.

A sample(autogenerated using intelliJ default) could be -

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

    Node<?> node = (Node<?>) o;

    if (left != null ? !left.equals(node.left) : node.left != null) return false;
    if (right != null ? !right.equals(node.right) : node.right != null) return false;
    if (parent != null ? !parent.equals(node.parent) : node.parent != null) return false;
    return value != null ? value.equals(node.value) : node.value == null;

}

@Override
public int hashCode() {
    int result = left != null ? left.hashCode() : 0;
    result = 31 * result + (right != null ? right.hashCode() : 0);
    result = 31 * result + (parent != null ? parent.hashCode() : 0);
    result = 31 * result + (value != null ? value.hashCode() : 0);
    return result;
}

---

On the other hand why

assertEquals(expectedList.toString(),tree.getValuesAtEachLevel().toString());

works.

It is because what you are tyring to assert finally here is compare two String instances which has its @Overriden equals definition here

Solution 2

Most likely because

new Node().equals(new Node()) == false

Override equals() and hashCode() in Node

Solution 3

Asserting that String representations of two objects are equals and these objects are equal are two distinct things.
The Object equality relies on the boolean equals(Object o) method from the Object class.
int hashcode() can improve the performance if overrided in a symmetric way to equals(Object o) method rather than returning a unique value in any case(by default) but for the assertion, it doesn't change the result. A good practice is overriding both when you override equals().

In your case, you have multiple ways of proceeding. I propose you 3 common ways:

• overriding equals() and hashcode() it their properties allow to define them in a way where it defines really the identity of the object. overriding equals() and hashcode() to make successful assertion in unit test is not enough to override the method.
  Besides, equals() overriding may be suitable for this test and not suitable for another test.
  The implementation of equals() and hashcode() method has to be conform to the way to identify the object and how you use this class in your application, not only for unit testing assertions.
  Here is another post where the question is asked : Should one override equals method for asserting the object equality in a unit test?

• doing the assertions in the loop.

For example, loop on the actual result and do the assertion node by node by using the 2D array you created for the expected result :

int i=0;

for (List<Node<Integer>>> listOfNodes :  tree.getValuesAtEachLevel()) {

    int j=0;

    for (Node node : listOfNodes ) {
        list.add(new Node<>(value));
       // I called the method getValue() because I don't know the getter
        Assert.assertEquals(expectedArray[i][j], node.getValue(); 
         // You could also display a JUnit failure message if you want
        j++; 
    }

    i++;
}

It way of proceeding may be clumsy and time consuming if you have to do assertions for your List of List in several other scenarios and the way to do the assertions is very different. But with a suitable code refactoring , we can extract util asserting methods in a reusable way in many scenarios.

• A alternative solution I like a lot is reflection for the assertions.

the Unitils library provides this feature and other things.

http://www.unitils.org/tutorial-reflectionassert.html

With Unitils, you could do :

ReflectionAssert.assertReflectionEquals(expectedList, tree.getValuesAtEachLevel());

without overiding equals(Object o) and hashcode().
The other advantage of Unitils is the rather friendly message if the assertion fails.

Comments

[Klaus Groenbaek]

Correct. assertEquals ends up calling expected.equals(actual) if none of the parameters are null. equals() for ArrayList compares elements in order, so if it doesn't work chances are that Node does not have a correct equals implementation so it gets the default (identity) equals provided by Object. The Node class needs to implement equals (and hashCode) that includes it's own value and the value of all children (if these are in a array list you just do equals on the child-list).