For 4 keys there are 14 possible trees, and they have frequencies {1,1,1,1,1,1,1,1,2,2,3,3,3,3}. I'm not sure what kind of distribution that is, but it's certainly not binomial.
For 5 keys there are 42 possible trees. 16 occur once, 4 occur twice, 8 occur three times, 8 occur four times, 4 occur six times, and 2 occur eight times.
For 6 keys there are 132 possible trees. 32 occur 1 time, 8 occur 2 times, 16 occur 3 times, 16 occur 4 times, 16 occur 5 times, 8 occur 6 times, 4 occur 8 times, 20 occur 10 times, 8 occur 15 times, and 4 occur 20 times.
For 7 keys there are 429 possible trees. 64 occur 1 time, 16 occur 2 times, 32 occur 3 times, 32 occur 4 times, 32 occur 5 times, 48 occur 6 times, 8 occur 8 times, 40 occur 10 times, 8 occur 12 times, 48 occur 15 times, 16 occur 18 times, 24 occur 20 times, 16 occur 24 times, 8 occur 30 times, 8 occur 36 times, 8 occur 40 times, 16 occur 45 times, 4 occur 48 times, and 1 occurs 80 times.
The number of trees for any number of nodes is a Catalan number (
A000108).
For a tree with nodes 1 through n and root x, the number of ways of getting that tree is (n-1 choose x-1) times the product of the number of ways of getting the trees on each side of x.
For n>k+1, the number of tree structures for n nodes that occur k times will be exactly twice the number of tree structures for n-1 nodes that occur k times.
For any n and k, the number of tree structures for n nodes that occur k times will be at least twice the number of tree structures for n-1 nodes that occur k times.
For any n and k, the number of tree structures for n nodes that occur k times is even, unless n is 1 less than a power of 2, where there is a unique k (the corresponding term from
A056972) for which there is exactly one tree structure that occurs k times. This tree structure is the perfectly balanced one.
For any prime p>2, the number of tree structures for p+1 nodes that occur p times will be 2^(p-1), and there will be no tree structures for any fewer number of nodes that occur p times.
