On the Co-Structure of $k$ Paths In a Random Binary Tree

Abstract

Consider the paths ${\pi }_t(i_1),\dots ,{\pi }_t(i_k)$ from the root to the leaves $i_1,\dots ,i_k$ in a random binary tree $t$ with $n$ internal nodes, where all such trees are assumed equally likely and the leaves are enumerated from left to right. We investigate, for fixed $i_1,\dots ,i_k$ and $n$, the average size of ${\pi }_t(i_1)\cup \dots \cup {\pi }_t(i_k)$ resp. of ${\pi }_t(i_1)\cap \dots \cap {\pi }_t(i_k)$ (the latter corresponding to the average depth of the smallest subtree containing $i_1,\dots ,i_k$). By a rotation argument, both problems are reduced to the case $k=1$, for which a solution is known. Furthermore, formulas for the probability distributions of the depth of leaf $i$, the distance between leaf $i$ and $j$ and the length of ${\pi }_t(i)\cap {\pi }_t(j)$ are derived.