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
}
}