Using Polymorphism instead of Conditionals

It was then that I decided I wanted to try and find out if the candidates really understood polymorphism and other concepts, rather than their knowledge of algorithms, since every other interviewer would be covering that. And that was when I stumbled upon this gem of a question, which also underlies a fundamental concept of object oriented programming.

The question is simple. “Given a mathematical expression, like 2 + 3 * 5, which can be represented as a binary tree, how would you design the classes and code the methods so that I can call evaluate() and toString() on any node of the tree and get the correct value.”. Of course, I would clarify that populating the tree was out of the scope of the problem, so they had a filled in tree to work with. It also gives me a chance to figure out how the candidate thinks, whether he asks whether filling in the tree is his problem or whether he just assumes stuff. You could preface this question with another about Tree’s and traversal to check the candidate’s knowledge and whether this one would be a waste of time or not.

Now, one of three things can happen at this point. One, the candidate has no clue about trees and traversals, in which case there is no point proceeding down this line. Second, which seems to happen more often than not, is the candidate gives a class and method like the following :

class Node {
    char operator;
    int lhsValue, rhsValue;
    Node left, right;

    public int evaluate() {
      int leftVal = left == null ?
          lhsValue : left.evaluate();
      int rightVal = right == null ?
          rhsValue : right.evaluate();
      if (operator == '+') {
        return leftVal + rightVal;
      } else if (operator == '-') {
        // So on and so forth.
        // Same for toString()
      }
  }
}

Whenever I see code like the example above, it just screams that whoever is writing it has no clue about how to work with Polymorphism. While I agree that some conditionals are needed, like checks for boundary conditions, but when you keep working with similar variables, but apply different operations to them based on condition, that is the perfect place for polymorphism and reducing the code complexity.

In the above case, the biggest problem is that all the code and logic is enclosed in a single method. So when a candidate presents me with this solution, the first thing I ask is what happens when we need to add another operation, like division or something. When the prompt answer is that we add an if condition, that is when I prompt and ask if there is not a cleaner solution, which would keep code separate. Finally, often, you depend on third party libraries for functionality. Well, in those cases, you won’t be able to edit the original source code, leaving you cursing the developer who wrote it for not allowing an extensible design.

The ideal answer would, for this question, be that Node is an interface with evaluate() and toString(). Then, we have different implementations of Node, like a ValueNode, an AdditionOperationNode, and so on and so forth. The implementations would look as follows :

interface Node {
  int evaluate();
  String toString();
}

public class ValueNode
    implements Node {
  private int value;
  public int evaluate() {
    return value;
  }
  public String toString() {
    return value + "";
  }
}

public class AdditionOperationNode
    implements Node {
  Node left, right;
  public int evaluate() {
    return left.evaluate()
        + right.evaluate();
  }
  public String toString() {
    return left.toString() + " + "
        + right.toString();
  }
}

You could go one step further and have an abstract base class for all operations with a Node left and right, but I would be well satisfied with just the above solution. Now, adding another operation is as simple as just adding another class with the particular implementation. Testing-wise, each class can be tested separately and independently, and each class has one and only one responsibility.

Now there are usually two types of conditionals you can’t replace with Polymorphism. Those are comparatives (>, <) (or working with primitives, usually), and boundary cases, sometimes. And those two are language specific as well, as in Java only. Some other languages allow you to pass closures around, which obfuscate the need for conditionals.

Of course, one might say that this is overkill. The if conditions don’t really make it hard to read. Sure, with the example above, maybe. But when was the last time you had just one level of nesting? Most times, these conditionals are within conditionals which are within loops. And then, every bit of readability helps. Not to mention there is a combinatorial explosion of the amount of code paths through a method. In that case, wouldn’t it be easier to test that the correct method is called on a class, and just test those individually to do the right thing?

So next time you are adding a conditional to your code, stop and think about it for a second, before you go ahead and add it in.