1
\$\begingroup\$

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
   }
 }
\$\endgroup\$
4
  • 2
    \$\begingroup\$ What happens if you need to add a child to a leaf node? Does it have to be replaced with a non-leaf node? Having different types for leafs and non-leafs seems like a bad idea. \$\endgroup\$
    – JS1
    Aug 24, 2017 at 20:12
  • \$\begingroup\$ @JS1 why would I add child to leaf? leaf by definition has no child. \$\endgroup\$
    – CodeYogi
    Aug 24, 2017 at 20:13
  • \$\begingroup\$ Because most trees can grow and shrink as you add/remove elements from it. Your tree can only remain static. \$\endgroup\$
    – JS1
    Aug 24, 2017 at 20:15
  • \$\begingroup\$ @JS1 you are on wrong track, I would create a new tree instead. \$\endgroup\$
    – CodeYogi
    Aug 24, 2017 at 20:16

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I chose NullNode because I don't want to explicitly check for null for example refer third case, how would you write with null? \$\endgroup\$
    – CodeYogi
    Aug 24, 2017 at 21:18
  • \$\begingroup\$ I would leave out the nodes completely. Or maybe only allow a NullNode as the root of the tree. But all non-leaf nodes should be properly filled with more non-leafs or leafs. \$\endgroup\$ Aug 24, 2017 at 21:22
  • \$\begingroup\$ I think we need not think of memory I would give priority to readability. \$\endgroup\$
    – CodeYogi
    Aug 24, 2017 at 21:24

Your Answer

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

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