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.

enter image description here

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!

  • 2
    $\begingroup$ Is your distribution on trees uniform over all trees (if so, what class of trees, exactly, e.g. for nodes with one child, do you distinguish between it being the left and right child)? Or do you have some random process in mind for generating trees? Is N a random variable, or is it given (and you are somehow conditioning on the tree having N leaves)? The node numbers are given by an inorder traversal? $\endgroup$
    – Neal Young
    Jul 30, 2021 at 2:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.