6
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Recursion is itself a code smell \$\endgroup\$ Jul 17, 2016 at 16:19
  • 7
    \$\begingroup\$ @BradThomas that statement is possibly the most offensive and stupid statement about programming that I heard in months. Congratulations. Recursion is a standard approach for method / function behaviour in all languages \$\endgroup\$
    – Vogel612
    Jul 17, 2016 at 16:48
  • 1
    \$\begingroup\$ "Standard" means nothing. Bad practice is also "standard" across the industry, in all languages. I have never come across a meaningful use of recursion (outside of academic interest) that could not be more readably and maintainably coded without the use of recursion. \$\endgroup\$ Jul 17, 2016 at 16:50
  • \$\begingroup\$ @Brad Thomas care to elaborate? I have read similar in the power of ten rules but cant really follow the Argumentation \$\endgroup\$
    – AdHominem
    Jul 17, 2016 at 17:17
  • 1
    \$\begingroup\$ Recursion is used for the sake of purported brevity, elegance but has a heavy cost in terms of readability and maintainability. I'm not saying it's never the most appropriate solution, only that I believe it is widely over-used for most line-of-business applications. In contrast to academic study questions, these applications are often in service over many years and require considerable ongoing maintenance. IMO a simpler flat enumeration over the tree would often suffice and be easier to analyze and maintain in most cases. Being widely over-used makes it a code smell i.e. likely inappropriate \$\endgroup\$ Jul 17, 2016 at 17:27

1 Answer 1

8
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Note that the modified version where you shift it to the node allocates a list for each node which is pretty wasteful \$\endgroup\$ Jul 17, 2016 at 15:30
  • \$\begingroup\$ @WorldSEnder Any idea how to circumvent this? \$\endgroup\$
    – AdHominem
    Jul 17, 2016 at 17:40
  • \$\begingroup\$ @Tunaki Really good points, I thought about the infix being a Node function as well! \$\endgroup\$
    – AdHominem
    Jul 17, 2016 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.