Probability Distribution Function of the Height of Nodes in Full Binary Trees

188 Views Asked by At

I would like to understand the distribution of node heights in the space of full binary trees with a fixed number of leaves, $n$. That is, given a random full binary tree with $n$ leaves how likely is it that there will be a leaf with height equal to one? Given the relationship between such trees and Catalan numbers (see below) I expect there are some results out there but I am having trouble finding good sources and references.

Additional Context

A full binary tree is a binary tree such that each node has either zero or two children. For example, the $(n-1)$st Catalan Number is the number of distinct full binary trees with $n$ leaves. Below is a picture of the $C_3 = 5$ full binary trees with four leaves:

Full binary trees with four leaves. (Public Domain)

In this example we see that,

$$ \begin{align} \mathbb{P}[\text{height} = 1] &= 0.2, \quad \textit{(four nodes out of twenty)}\\ \mathbb{P}[\text{height} = 2] &= 0.4, \\ \mathbb{P}[\text{height} = 3] &= 0.4, \\ \mathbb{P}[\text{height} = 4] &= 0.0, \\ & \;\,\vdots \end{align} $$

Given a number of leaves, $n$, is there a general formula for this height distribution? Is there an appropriate continuous version of this distribution? In my search I've found statements about the height of the trees but not the heights of the leaves of the trees.