Enumeration of tree properties by naive methods

This paper studies the problem of how much space is saved, on average, when a TRIE is pruned back to a minimal discriminating prefix. Exact figures (on average, half the space is saved) are given for binary trees. All treens with n nodes and m leaves are assumed equally likely. The calculations are based on an unusual form of recurrence relation.