Count number of leaves in binary tree Description:

Given a binary tree find the number of leaves. Although the problem is simple and has been solved many times I am more interested in find object oriented ways to solve the algorithmic problems.

Code:

interface Node {
   public int count();
 }

 class LeafNode implements Node {
   LeafNode() {}

   public int count() {
     return 1;
   }
 }

 class NonLeafNode implements Node {
   private Node left;
   private Node right;

   NonLeafNode(Node left, Node right) {
     this.left = left;
     this.right = right;
   }

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

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

 public class Main {
   public static void main(String[] args) {
     Node tree = new LeafNode();
     System.out.println(tree.count()); // 1

     tree = new NonLeafNode(new LeafNode(), new LeafNode());
     System.out.println(tree.count()); // 2

     tree = new NonLeafNode(
       new NonLeafNode(new LeafNode(), new NullNode()), new NullNode());
     System.out.println(tree.count()); // 2
   }
 }
You said in one of the comments that instead of modifying an existing tree, you would rather create a new tree. In this case, having separate classes for the nodes is acceptable (I wouldn't do it, though). But then, to effectively communicate that you are not going to modify the nodes, all their fields must be final.

I don't understand why you need the NullNode. To me it looks like a waste of memory.

The empty default constructor of LeafNode is unnecessary. In the NullNode class you didn't write it out explicitly, which is better.

At the end of your program you have these lines:

tree = new NonLeafNode(
  new NonLeafNode(new LeafNode(), new NullNode()), new NullNode());


As it is written right now, as a reader I have to carefully count parenteses to see which nodes belong together. This is because the text Node(), new appears almost 3 times. I prefer the following form:

tree = new NonLeafNode(
  new NonLeafNode(new LeafNode(), new NullNode()),
  new NullNode());


Or, if the structure gets even more complicated:

tree = new NonLeafNode(
  new NonLeafNode(
    new LeafNode(), 
    new NullNode()),
  new NullNode());


The indentation now corresponds exactly to the depth of the node in the tree. Well, except for the root node, but that should be easy to figure out.

All in all it is a very nice piece of code. You chose really good names for the classes and variables, which is one of the most important things in programming. I also liked that you wrote the expected output in comments. For code that you show to others, this is good so that they don't have to run the code. When you do serious programming, you should replace those comments with proper unit tests.