Planar binary trees with MetaPost

I recently needed to draw planar binary trees (PBT) for a paper I wrote with my collaborator. The paper is written in plain TeX with a minimal set of macros from a modified version of harvmac (named harvmacM).

At first I used tikz since it works with plain TeX. The drawback is that for each PBT one needs to write down the precise Cartesian coordinates for the root and each of its leaves.

After some boring time wasted with tikz, I decided to write a general macro to draw planar binary trees with MetaPost. The result looks nice. Furthermore, there is no need to manually specify the coordinates of the leaves, just how they are related to each other.

For example,

prologues:=3;
filenametemplate "%j-%c.eps";
defaultscale := 3.4;
u := 5.5cm;
input PBT.mp;

beginfig(1);
pickup pencircle scaled 3.8bp;
setupLegs(5);
i2 := whatever[bL2,t2] = whatever[origin,t1];
i3 := whatever[bL3,t3] = whatever[origin,t1];
i4 := whatever[bL4,t4] = whatever[origin,t1];
drawPBT(origin, 5);
endfig;


and,

beginfig(2);
pickup pencircle scaled 3.8bp;
setupLegs(5);
i2 := whatever[bL2,t2] = whatever[origin,t1];
i3 := whatever[bR3,t3] = whatever[bL4,t4];
i4 := whatever[bL4,t4] = whatever[origin,t1];
drawPBT(origin, 5);
endfig;


So one can see that the iN positions mean the intersection points of the leaves, where the leaf 1 is the line [origin, t1], leaf 3 is [bL3, t3] if its angle is 45 degrees or [bR3, t3] if its angle is 135 degrees and so forth. Very easy to specify and the calculations to find the coordinates of the intersection points are done by MetaPost.

The macros below can be put in a file PBT.mp and loaded with "input PBT.mp". They contain the coordinates Hoffset and Voffset which are useful when drawing more than one tree in the same figure. The first parameter of drawPBT() specifies the position of the root, so e.g. drawPBT(origin, 5); and drawPBT(Hoffset, 5);  would draw the diagrams shifted horizontally by the amount Hoffset.

pair t[], i[]; % top and intersection points
pair bL, bL[], bR, bR[]; % bottom left and right
pair Hoffset, Voffset, V;

def setupLegs(expr n) =
% n is the number of leaves, u is the scale

t1     := (-1.0u, 1.0u); % first leg
t[n]   := (+1.0u, 1.0u); % last leg
t[n+1] := (0.0u, -0.3u); % the offshell leg is defined as the (N+1)-th leg
bL     := (-2.0u, 0.0u); % far bottom left
bR     := (+2.0u, 0.0u); % far bottom right
Hoffset := (2.7u,0.0u);   % horizontal offset between diagrams
Voffset := (0.0u,2.8u);   % vertical offset between diagrams
V      := (0.0u, -0.07u);
i[1]   := origin;   % first leg
i[n]   := origin;   % last leg
i[n+1] := origin;   % offshell leg

for i:=2 upto (n-1):
        if n = 2:
                t[2] := (1u,1u);
        else:
                j := ((i-1)/(n-1));
                t[i] := j[t1,t[n]];     % top of legs are always in the same position
                bL[i] := j[bL,origin];  % bottom projection can be either on left or right
                bR[i] := j[origin,bR];  % bottom projection can be either on left or right
        fi
endfor
enddef;

def drawPBT(expr offset, n) =
% offset is the (x,y) position of the root, e.g. (0,0)

for j:=1 upto (n+1):
        draw (i[j]--t[j]) shifted offset;
        if j < (n+1):
                label.top(decimal(j),(t[j] + (0u,0.05u))) shifted offset;
        fi
endfor
enddef;