Testing a method using recursion in binary search tree

Question

This toRoot method is supposed to return a list containing all the keys in the tree between the parameter key and the root. I have used a System.out.println statement in both the class and the junit test method. Why are the outputs of the two print statements different? The output printed in the toRoot method is what I want, but I am printing only the root in the junit test method. How do I fix this?

public List<K> toRoot(K key) {
        List<K> list=new LinkedList<K>();
        int i = key.compareTo(this.key);
        if(i == 0){
            list.add(this.key);
        }
        else if(i < 0){
            left.toRoot(key);
            list.add(this.key);
        }
        else if(i > 0){
            right.toRoot(key);
            list.add(this.key);
        }   
        System.out.print(list); //prints "i o n p s z i"...these are the desired 
        //outputs of the two assertEquals combined together
        return list;
    }

JUnit Testing

@Test public void testToRoot() {
    Tree<Character, Integer> tree = tree1();
    System.out.print(tree.toRoot('o')); //prints 'i'
    assertEquals("i", tree.toRoot('i'));
    assertEquals("o n p s z i", tree.toRoot('o'));
}
private static Tree<Character, Integer> tree1() {
    Tree<Character, Integer> tree = EmptyTree.getInstance();

    tree= tree.add('i', 1);
    tree= tree.add('z', 2);
    tree= tree.add('e', 3);
    tree= tree.add('s', 4);
    tree= tree.add('p', 5);
    tree= tree.add('n', 6);
    tree= tree.add('b', 7);
    tree= tree.add('h', 8);
    tree= tree.add('o', 9);
    tree= tree.add('f', 10);

    return tree;
}

additional details: The tree class is an interface that the NotEmptyTree class implements and includes an overwritten toRoot.

public NonEmptyTree<K, V> add(K key, V value);

Here is the overwritten add method in the NotEmptyTree class

public NotEmptyTree<K, V> add(K key, V value) {
        if(key.compareTo(this.key) == 0){
            this.value = value;
        }else if(key.compareTo(this.key) < 0){
            left = left.add(key, value);
        }else{
            right = right.add(key, value);
        }
        return this;    
    }

Letters near the front of the alphabet are smaller than those towards the end. In this case, 'i' is the parent node of 'e' and 'z'. 'z' has a left child of 's', which has left child of 'p', which has left child of 'n', which has right child of 'o'. 'e' has left child of 'b', which has right child of 'h'.

b4hand b4hand · Accepted Answer · 2014-11-16T00:43:56

Your toRoot method may be printing a string to System.out, but it does not return a String. Instead, it returns a List. Thus your assertion is going to be always false because a String does not equal a List.

If you want to compare against a String, then you'll need to write a function that converts a List<K> into a space delimited String and then invoke that function before calling assertEquals.

Another alternative, would be to use a Hamcrest-style matcher like contains:

assertThat(tree.toRoot(), contains('o', 'n', 'p', 's', 'z', 'i'));

Note that despite the name, the contains does an in-order check, so even if the keys were out of order this test would fail, which should give identical behavior to the assertEquals check you were making before.

Testing a method using recursion in binary search tree

1 Answers