# How to generate a random binary tree with a given number of vertices and with a given shape, namely compact or elongated

I tried to generate a random binary tree with a Table of RandomInteger and to give a shape with a LayerSizeFunction, but the degree of the node equal to 2 is not respected. I try also by KaryTree, but I'm not able to do it.

The folloing figures show an example of network compact and elongated, with 60 vertices, respectively:

Here is my attempt:

SeedRandom@0
TreePlot[Table[i -> RandomInteger[{0, i - 1}], {i, 1, 20}],
MultiedgeStyle -> None, SelfLoopStyle -> None,
LayerSizeFunction -> (1 # &)]


I doubt if 'random' and elongated/compact can be nicely combined, but you can get close. With n=60 (60 leaves), there are CatalanNumber[60] or about 1.58385*10^33 binary trees to choose from. They can be written as binary strings (or numbers) ordered from 1111 ... 0000 to 101010...101010 with, counting from left to right, at least as many 1's as 0's in the run. Trees can be ranked an unranked. If you consider the first quarter (rank 1 to cat[n]/4) as left-elongated, the last quarter (rank 3*cat[n]/4 to cat[n]) as right-elongated, then you could consider the middle half as compact-ish.
I have a few functions to do this. But it is such fun finding them that I will withhold the code as a spoiler, and let you have some fun too. Unless you're in a hurry and want it out of the way. Say the word and I'll spill the beans.

cattria[n_,m_]:=(n+m)!/(n+1)!/m!(n-m+1);
trapo[li:{__Integer}]:=Count[li,q_/;q>=#]&/@Range[Length[li]];trapo[{}]:={0};
toparti[li:{(1|0) ..}]:=Rest[Flatten[Position[li,1]]-Range[Length[li]/2]];

RankTree1[parti:{__Integer}]:=1+Plus@@Apply[cattria[#1+1,#2-1]&,Transpose[{Reverse@Range[Length[parti]],trapo[parti]}],1];
RankTree[li:{(1 | 0)..}] :=Sum[cattria[w,w],{w,1,Length[li]/2-1}]+ RankTree1[toparti[li]] ; RankTree[{1,0}]:=1 ;

NthTree1[w_Integer/;(w>0), o_Integer:1] := Module[{k = 0, therest, result = {}}, While[cattria[k, k] < w, k++]; k=Max[o,k];therest = w; While[k > 1, m = 0; While[cattria[k, m] < therest, m++]; therest -= cattria[k, m - 1]; AppendTo[result, m]; k--]; Reverse[trapo[result]]];

NthTree[w_Integer /; w > 0, o_Integer:1] := Module[{temp1, temp2}, Module[{k = 1, t = 1}, While[t + cattria[k, k] <= w, t += cattria[k, k]; k++]; w2 = w + 1 - t; o2 = k];
temp1 = NthTree1[w2, o2]; temp2 = Prepend[temp1, 0] + Range[Length[temp1] + 1]; MapAt[#1 + 1 & , 0*Range[2*Length[temp2]], Transpose[{temp2}]]]; NthTree[1] := {1, 0};


and, finally :

NthTreeLocal[w_Integer /; w > 0, o_Integer:1] := Module[{temp1, temp2}, Module[{k = 1, t = 1}, While[t + cattria[k, k] <= w, t += cattria[k, k]; k++]; w2 = w + 1 - t; o2 = k];
temp1 = NthTree1[w, o]; temp2 = Prepend[temp1, 0] + Range[Length[temp1] + 1]; MapAt[#1 + 1 & , 0*Range[2*Length[temp2]], Transpose[{temp2}]]]; NthTree[1] := {1, 0};

• I find it very interesting for the generation of binary trees with Catalan and it would be very useful for my work. Not to sound pushy, but if you could give me the code I would be very grateful. I tried but I'm not able to do it. – user15850 Jun 21 '14 at 12:26
• How about adding a picture of a Graph generated with your code? – Öskå Jun 21 '14 at 13:06
• @Öskå: I'll do that tomorrow, got to go now. – Wouter Jun 21 '14 at 13:26
• The primitive idea that average depth of the leaves varies smoothly and systematicaly as a function of rank was overly optimistic. Plotting average depth versus rank shows a succession of deep (elongated) and shallow (compact) zones. The good news is that the plot remains similar for sets of trees with more leaves. So the relative positions of shallow and deep zones seem to be independent of the leaf count. – Wouter Jun 22 '14 at 20:31