Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the tree.
Say you randomly select $M < N$ leaves. For each selected leaf, you perform a $\textit{pruning process}$ as follows. You delete the leaf. If the leaf was the only child of its parent, you delete the parent. If the parent was the only child of $\textit{its}$ parent, you delete this parent. And so on, deleting all nodes in a path until a node with two children is reached. The number of nodes deleted for a given leaf is the $\textit{prune length}$ of the leaf. The prune length of the first leaf to be removed will, of course, be one, but the subsequent prune lengths depend on the previous pruning processes and the structure of the tree.
For example, a pruning process starting at node 14 in the tree below would remove nodes 14, 15, and 13, resulting in a prune length of 3. A pruning process starting at node 0 would only remove node 0, resulting in a prune length of 1.
My question is: Across all random binary trees with $N$ leaves, where $M$ prune processes are performed for each tree, what is the distribution of the prune lengths? Does it follow some Poisson or power-law?
Thank you for any feedback!
