Code smell when recursively returning a List

Question

So this is part of my AVL tree implementation, namely the infix representation of the tree. Since I wanted to use a recursive method to stay close to the original algorithm and want to return a list, I have to store the values in a parameter.

The smelly part is in getInfix when I reference that parameter to return the list. I am not even sure what's the name of this code smell but it feels wrong. I am literally only calling getInfixInternal for its side effect! But I can't simply return a list either...

How can I make this better?

private List<T> getInfix() {
    List<T> result = new ArrayList<>();
    getInfixInternal(root, result);
    return result;
}

private void getInfixInternal(Node node, List<T> infixValues) {
    if (node != null) {
        getInfixInternal(node.getLeft(), infixValues);
        infixValues.add((T) node.getValue());
        getInfixInternal(node.getRight(), infixValues);
    }
}

My Node class (excluding the getters and setters for reasons of space):

public class Node <T extends Comparable>  {
    private T value;
    private Node leftChild;
    private Node rightChild;
    private Node parent;
}

Answer 1

I wouldn't say there is a code smell with what you have now. However, it could be made more OOP-friendly.

An actual problem is that you're using raw types for Node, and that is never a good idea. So, first of all, consider having this instead:

private List<T> getInfix() {
    List<T> result = new ArrayList<>();
    getInfixInternal(root, result);
    return result;
}

private void getInfixInternal(Node<T> node, List<T> infixValues) {
    if (node != null) {
        getInfixInternal(node.getLeft(), infixValues);
        infixValues.add(node.getValue());
        getInfixInternal(node.getRight(), infixValues);
    }
}

and

public class Node<T extends Comparable<? super T>>

Then, to avoid this getInfixInternal, you can reason with what the method getInfix means. The first thing to realize is that it works on a given Node. In fact, it is really a property of the node itself: every node can return a list of values resulting of a infix traversal of the subtree starting at this node. Therefore, instead of having an internal method taking a Node as parameter, make it a method of Node:

public class Node<T extends Comparable<? super T>> {

    // ...

    public List<T> getInfix() {
        List<T> result = new ArrayList<>();
        if (leftChild != null) {
            result.addAll(leftChild.getInfix());
        }
        result.add(value);
        if (rightChild != null) {
            result.addAll(rightChild.getInfix());
        }
        return result;
    }

}

With such a method, you can then have:

private List<T> getInfix() {
    return root == null ? Collections.emptyList() : root.getInfix();
}

With Java 8 Optional, you could potentially write that more concisely:

public List<T> getInfix() {
    List<T> result = new ArrayList<>();
    Optional.ofNullable(leftChild).map(Node::getInfix).ifPresent(result::addAll);
    result.add(value);
    Optional.ofNullable(rightChild).map(Node::getInfix).ifPresent(result::addAll);
    return result;
}

Final note: you could also consider returning unmodifiable lists.