BinaryTree.java

package dp;

interface Tree<K> {
	int leaves();
}

class Branch<K> implements Tree<K> {
	final Tree<K> left, right;
	
	Branch(Tree<K> left, Tree<K> right) {
		this.left  = left;
		this.right = right;
	}

	@Override
	public int leaves() {
		return this.left.leaves() + this.right.leaves();
	}
	
	@Override
	public String toString() {
		return "Branch [left=" + left + ", right=" + right + "]";
	}

}

class Leaf<K> implements Tree<K> {
	final K key;
	
	Leaf(K key) {
		this.key = key;
	}

	@Override
	public int leaves() {
		return 1;
	}
	
	@Override
	public String toString() {
		return "Leaf [key=" + key + "]";
	}

}

class BinaryTree {
	public static void main(String[] args) {
		Tree<String> t = full(10, "foo");
		
		System.out.println(t);
		System.out.println(t.leaves());
	}
	
	static <K> Tree<K> full(int h, K key) {
		if(h > 0) {
			return new Branch(full(h-1, key), full(h-1, key));
		} else {
			return new Leaf(key);
		}
	}
}