The disadvantage of poly here is more code and more classes. Yes, you can add a new operator without modifying the node class - but now you must modify the tree-populating code instead.
- You have reduced the cyclomatic complexity of each class, which makes the code less fragile and easier to unit test.
- When adding a new operator, you are now forced to implement everything it needs to work. If you don't define a method, it won't compile. This is not the case with a long list of if/else statements.
- "You still need a nest of conditionals when you populate the tree..." This is true, but now all the conditionals are in one place, rather than two (in their example, toString and evaluate). Again, this will make testing easier.
I try to take this as far as I can. For instance, when writing Servlet code in Java, I define all my request parameter names in an enum, so that I can never misspell any lest the compiler tell me.