Tree.hs

module Tree where

data Expr = Digit Int
          | Complex Expr Expr Expr
          deriving (Show)

generateAll :: Int -> [Expr]
generateAll 1 = [Digit 0, Digit 1]
generateAll n | n <= 0 = []
generateAll n = do
  s1 <- [1 .. n - 1]
  s2 <- [1 .. n - s1 - 2]
  let s3 = n - s1 - s2 - 1
  e1 <- generateAll s1
  e2 <- generateAll s2
  e3 <- generateAll s3
  return $ Complex e1 e2 e3

main = print $ length $ generateAll 7

Trees.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Trees {

    static interface Expr {
        public abstract int size();
    }

    static class Digit implements Expr {
        public final int digit;

        @Override
        public int size() {
            return 1;
        }

        Digit(int digit) {
            if (digit < 0 || digit > 9)
                throw new IllegalArgumentException("supply a digit");
            this.digit = digit;
        }

        @Override
        public String toString() {
            return Integer.toString(digit);
        }
    }

    static class ComplexExpr implements Expr {
        public final Expr e1, e2, e3;

        @Override
        public int size() {
            return 1 + e1.size() + e2.size() + e3.size();
        }

        ComplexExpr(Expr e1, Expr e2, Expr e3) {
            this.e1 = e1;
            this.e2 = e2;
            this.e3 = e3;
        }

        @Override
        public String toString() {
            return String.format("(tree %s %s %s)", e1.toString(), e2.toString(), e3.toString());
        }
    }

    static List<Expr> generateAll(int size) {
        if (size <= 0)
            return Collections.emptyList();

        List<Expr> result = new ArrayList<>();

        if (size == 1) {
            for (int i = 0; i < 2; i++) {
                result.add(new Digit(i));
            }
        } else {
            for (int s1 = 1; s1 < size; s1++) {
                for (int s2 = 1; s1 + s2 + 1 < size; s2++) {
                    int s3 = size - s1 - s2 - 1;
                    for (final Expr e1 : generateAll(s1)) {
                        for (final Expr e2 : generateAll(s2)) {
                            for (final Expr e3 : generateAll(s3)) {
                                result.add(new ComplexExpr(e1, e2, e3));
                            }
                        }
                    }
                }
            }
        }

        return result;
    }

    public static void verify(int size) {
        for (final Expr expr : generateAll(size)) {
            if (expr.size() != size)
                throw new RuntimeException("generateAll is incorrect!");
        }
    }

    public static void main(String[] args) {
        int SIZE = 7;

        final List<Expr> exprs = generateAll(SIZE);
        for (final Expr expr : exprs) {
            System.out.println(expr);
        }

        verify(7);
        System.out.println(exprs.size());
    }

}