What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves?
To be honest, I'm unsure about whether this is a CS question or a programming question. There is a strong programming part to it, yet encoding requirements in types requires reasoning on types which is more on the CS side. Anyway, here is an answer.



There are several options to encode that requirement into types.

Basically, we need to encode that each BranchNode has at least one child. This means that a leaf can only be a LeafNode.

A naive approach would be

final class BranchNode&lt;T&gt; implements Node&lt;T&gt; {
    Node&lt;T&gt; firstChild;
    List&lt;Node&lt;T&gt;&gt; otherChildren;
}


We can even keep only a (private) children list, and enforce that using a constructor.

// Make these private
private Node&lt;T&gt; firstChild;
private List&lt;Node&lt;T&gt;&gt; otherChildren;

// Make this to be the only public constructor of the class
BranchNode(Node&lt;T&gt; firstChild, List&lt;Node&lt;T&gt;&gt; otherChildren) {
    children = otherChildren.clone();
    children.add(firstChild);
}


Note the usual caveats, though. One can break this invariant using nulls, non termination, or by creating circular references, e.g. a BranchNode which is its own child (this is easy to achieve if the tree is mutable, for instance). Unwanted subclasses also can break the invariant.



Another option is to exploit the usual Church encoding of algebraic data types into polymorphic types. In theory, this is related to initial algebras and catamorphisms. In OOP practice, this is known as the "visitor pattern".

I'll pretend leaves contain a single int. One can generalize this using generics, as usual.

interface Visitor&lt;R&gt; {
   R visitNode(int data);
   R visitBranch(R firstChild, List&lt;R&gt; otherChildren);
}

interface Node {
   &lt;R&gt; R visit(Visitor&lt;R&gt; v);
}


Pseudo code follows, since Java is too heavy for writing this in a readable way, and I'm not completely familiar with its functional libraries.

class LeafNode implements Node {
  int data;
  visit(v) = v.visitNode(data);
}

class BranchNode implements Node {
  Node firstChild;
  List&lt;Node&gt; otherChildren;
  visit(v) = v.visitNode(firstChild.visit(v),
                         otherChildren.map(_.visit(v)));
}


The advantage of this approach is that the invariant can not really be broken by adding subclasses. One can create a new Leaf2Node subclass, but if that has the same visit(v), it will behave as LeafNode. The implementation of visit(v) in general will be limited by types, and running visit(v) will always (if terminating) end with calling v.visitNode(data) when a leaf is encountered.