# linking cousins in a binary tree

I constructed the horizontal links between some pairs of first, second and third cousins in this binary tree by hand. I'd like a tikz solution. The particular links can be hard coded. It would be nice if I could experiment with line weights. Edit: Here's how to determine the connected cousins.

In a binary tree a pair of nodes are $k$th cousins for a node $N$ if they are on level $k+1$ below $N$ and $N$ is their nearest common ancestor. $0$th cousins are siblings. There are $2^{2k}$ pairs of of $k$th cousins, since you can form such a pair by choosing on cousin from the left half of the tree below $N$ and one from the right half.

Among those pairs we single out $2^k$ pairs of \emph{kissing
cousins}. If you number the nodes at level $k+1$ below $N$ as $1,2,\ldots,2k$ in the left and right halves then the kissing $k$th cousins are the pairs

(2,1), (4,2), \ldots, (2k,k)

The figure shows the kissing cousin pairs for node 1 (solid lines) and node 3 (dashed lines).

MWE:

%Tree showing kissing cousins
\documentclass{standalone}
\usepackage{tikz-qtree}
\begin{document}
\begin{tikzpicture}[every tree node/.style={draw,circle},
level distance=1.25cm,sibling distance=.05cm,
edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}]

\Tree [.1
[.2
[.4
[.8
[.16
]
[.24
]
]
[.12
[.32
]
[.36
]
]
]
[.6
[.16
[.36
]
[.48
]
]
[.18
[.52
]
[.54
]
]
]
]
[.3
[.8
[.18
[.41
]
[.54
]
]
[.24
[.66
]
[.72
]
]
]
[.9
[.26
[.60
]
[.78
]
]
[.27
[.80
]
[.81
]
]
]
] ]
\end{tikzpicture}
\end{document}


Here is a proposal. You can make the single entries nodes, which then can be accessed by ordinary TikZ commands. To simplify life a bit, I defined a style which does the u-shape connections. And of course you can adjust the line styles (widths, color, dashed) as you like. (EDIT: Fixed the issue of overlapping connections.)

\documentclass[border=3.14mm]{standalone}
\usepackage{tikz-qtree}
\usetikzlibrary{calc}
\begin{document}
\tikzset{connect u/.style=
{to path={let \p1=($(\tikztotarget)-(\tikztostart)$),
\n1={ifthenelse(\x1>0,-85,-95)},
\n2={ifthenelse(\x1>0,-95,-85)}
in
(\tikztostart.\n1) -- ++(0,-#1) -|  (\tikztotarget.\n2)
}}}
\begin{tikzpicture}[every tree node/.style={draw,circle},
level distance=1.25cm,sibling distance=.05cm,
edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},
remember picture]
\Tree [.1
[.2
[.4
[.8
[.16
]
[.\node(24a){24};
]
]
[.\node(12){12};
[.32
]
[.\node(36){36};
]
]
]
[.\node(6){6};
[.16
[.36
]
[.\node(48){48};
]
]
[.\node(18a){18};
[.52
]
[.\node(54a){54};
]
]
]
]
[.3
[.\node(8){8};
[.\node(18b){18};
[.\node(41){41};
]
[.\node(54b){54};
]
]
[.\node(24b){24};
[.\node(66){66};
]
[.\node(72){72};
]
]
]
[.9
[.\node(26){26};
[.\node(60){60};
]
[.\node(78){78};
]
]
[.27
[.80
]
[.81
]
]
]
] ]
\draw[thick] (6) -- (8);
\draw[thick] (12) edge[connect u=3pt] (18b);
\draw[thick] (18a) edge[connect u=6pt] (24b);
\draw[densely dashed] (24b) -- (26);
\draw[thick] (24a) edge[connect u=3pt] (41);
\draw[thick] (36) edge[connect u=6pt] (54b);
\draw[thick] (48) edge[connect u=9pt] (66);
\draw[thick] (54a) edge[connect u=12pt] (72);
\draw[densely dashed] (54b) edge[connect u=3pt] (60);
\draw[densely dashed] (72) edge[connect u=6pt] (78);
\end{tikzpicture}
\end{document} Of course I am biased but I would probably switch to forest. This allows one to see the binary structure more explicitly. Using this nice answer by @cfr, one can name the nodes in a binary in a binary fashion. For instance, the node 2 at level 2 (the uppermost node has level 1 in this convention) would be called node-1, and the node right of it node-2. At level 3, the leftmost node has the name node-1-1, then comes node-1-2, then node-2-1 and node-2-2, and so on. This notation seems to make the notion cousins more plausible: cousins have the same number of 1s and 2s. In particular, you do not have to invent names for the nodes, forest does that for you, and it is then very easy to draw the cousin connections. One may even automatize that, but unfortunately I do not precisely understand the definition of "cousin", and you also seem to want different line styles, so I do that by hand.

\documentclass[border=10pt,multi,tikz]{standalone}
\usepackage[edges]{forest}
\usetikzlibrary{calc}
\begin{document}
\tikzset{connect u/.style=
{to path={let \p1=($(\tikztotarget)-(\tikztostart)$),
\n1={ifthenelse(\x1>0,-85,-95)},
\n2={ifthenelse(\x1>0,-95,-85)}
in
(\tikztostart.\n1) -- ++(0,-#1) -|  (\tikztotarget.\n2)
}}}
\begin{forest}
for tree={
align=center,
draw,
circle,
l sep'+=15pt,
},
my label/.style={alias=node-#1,
% uncomment this if you want to see the node names
%label={[anchor=south east]above:#1},
},
before typesetting nodes={
for descendants={
temptoksa/.option=n,
for nodewalk={
while={>On>{level}{1}}{u,+temptoksa=-,+temptoksa/.option=n}
}{},
my label/.register=temptoksa,
},
}
[1
[2
[4
[8
[16
]
[24
]
]
[12
[32
]
[36
]
]
]
[6
[16
[36
]
[48
]
]
[18
[52
]
[54
]
]
]
]
[3
[8
[18
[41
]
[54
]
]
[24
[66
]
[72
]
]
]
[9
[26
[60
]
[78
]
]
[27
[80
]
[81
]
]
]
]
]
\draw[thick] (node-2-1) -- (node-1-2);
\draw[thick] (node-1-1-2) edge[connect u=3pt] (node-2-1-1);
\draw[thick] (node-1-2-2) edge[connect u=6pt] (node-2-1-2);
\draw[densely dashed] (node-2-1-2) -- (node-2-2-1);
\draw[thick] (node-1-1-1-2) edge[connect u=3pt] (node-2-1-1-1);
\draw[thick] (node-1-1-2-2) edge[connect u=6pt] (node-2-1-1-2);
\draw[thick] (node-1-2-1-2) edge[connect u=9pt] (node-2-1-2-1);
\draw[thick] (node-1-2-2-2) edge[connect u=12pt] (node-2-1-2-2);
\draw[densely dashed] (node-2-1-1-2) edge[connect u=3pt] (node-2-2-1-1);
\draw[densely dashed] (node-2-1-2-2) edge[connect u=6pt] (node-2-2-1-2);
\end{forest}
\end{document} • Thanks. I haven't decided yet which version to use. It won't matter much since I need this figure just once for one paper. I've edited the question to explain just which cousin pairs are linked, should you be curious. – Ethan Bolker Aug 6 '18 at 0:28
• @EthanBolker I see. Yes, I am curious. Not sure if I could do that programmatically in such a way that the connect u shifts would also come automatic (but I am sure cfr could), yet I could try to add the lips for "kissing" if you think it's worthwhile. (Is there a simple formula to determine "kissing" cousins. It is obvious that their binary labels are related by permutations, but is it clear which permutation?) – user121799 Aug 6 '18 at 1:49
• I'm currently finishing the paper that uses these cousins. If you send me email (see my profile) I'll send you the final draft, where you can see the formal definition of kissing cousins using paths in the tree. I don't need a coded solution for this image. – Ethan Bolker Aug 6 '18 at 14:03