Count number of nodes in a binary tree the OO way I am trying to write a simplify the algorithm of finding the number of nodes in a binary tree by using good object oriented design. I have been into good OOP style recently and found it really compelling in way that it can simplify the mental load by proper polymorphism.

Having said that, I don't know if it's a right strategy to follow in the interview since it may take some time to get to a good design.

import java.util.*;
import java.lang.*;
import java.io.*;


interface Node {
    public int count();
}

class Empty implements Node {
    public int count() {
        return 0;
    }
}

class NonEmpty&lt;Item&gt; implements Node {
    private final Item item;
    private final Node left;
    private final Node right;

    NonEmpty(Item item) {
        this(item, new Empty(), new Empty());
    }

    NonEmpty(Item item, Node left, Node right) {
        this.item = item;
        this.left = left;
        this.right = right;
    }

    public int count() {
        return left.count() + right.count() + 1;
    }
}

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Node n = new Empty();
        System.out.println(n.count()); // 0

        // Single node tree
        n = new NonEmpty(5);            
        System.out.println(n.count()); // 1

        // Complete Full tree       
        n = new NonEmpty(5, new NonEmpty(2), new NonEmpty(6));
        System.out.println(n.count()); // 3

        // Right skewed
        n = new NonEmpty(5, new NonEmpty(2, new NonEmpty(6), new Empty()), new Empty());
        System.out.println(n.count()); // 3
    }
}


I am thinking to write some common Tree based algorithm this way and see how far I can go.

Questions:


Is this a good strategy for interviews?
Have I divided the responsibility correctly?
Does this scale well to other tree-based algorithms?


Major Doubt:

I have seen in books such as this the author focuses on different classes like for above it could be:

class CountNodes {
  public CountNodes(Node n) {
    //...
  }
}


Which is a better strategy?
I agree with the other posters that a visitor pattern would be a viable solution. One important reason being, that a node usually holds some payload, not just other nodes, and you want to have a mechanism that allows you to be very versatile on what you want to do with the data in the tree.

You may want to count the number of nodes, you might also want to count the number of nodes, where the payload matches some criteria, or you want to count the number of nodes that do not have a left and a right sub node or whatnot. You don't want your node to contain a method for every possible question you want to ask your tree.

You might want to read my blog post on the LOD and structure agnostic access for a rather freaked out, but general solution. But be warned it's possibly not the kind of code you might be used to and you might not find it particularly "pretty", as it trades type safety for "simplicity".

But a visitor is not the only good solution out there. You may prefer to implement a method that returns an iterator, or even a Stream of nodes. This way you could use the Java stream API and be very versatile.

As for the interview: I often feel that programming tasks in interviews are misplaced. The résumé should give you enough of an idea if you've got an experienced programmer or not. Once the person is hired, code conventions, code reviews and tests should shape the quality and style of the person's code to your needs anyway - and there's a probation period to see if the person is not up to your standards or toxic. The only thing that a little piece of code is good for, in my opinion, is to sort out freshmen and students who don't know how to code, but claim to do so. In job interviews I might like to talk about a piece of code and discuss its style, not for the sake of labeling the answers "right" or "wrong", but to see how they think about code: Are they the pragmatic kind of programmer, are they code-poets with a love of style and readability, will you have to brake their tendency for over-engineering or will you have to nurse them a bit more? Do they make good points, are they the timid or the outspoken kind of person? You might feel you lack the one or the other kind in your team and that might make a difference in the end. But I feel that, if I look at a résumé with plenty of projects on it, that I should be able to assume they know how to code and I don't want to insult them with giving them programming tasks that are not related to their daily work at this company, but rather to their first year in algorithms and data structures class.

Discussing your piece of code above, I would, for example find it perfectly reasonable, if the candidate said: "This is a pragmatic solution for counting nodes and maybe something similar, so if that's all there is to it, I'd be fine with it. Still, if it is foreseeable that we need more than just two or three queries, we should have another object do the query." That'd be bang on.