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. This paper was originally published in Algorithms review 1:3, September 1990, 119--124, a journal which lasted from 1990 to 1992.