Leaf Stripping on Uniform Attachment Trees

• Authors: Louigi Addario-Berry, Anna Brandenbergen, Simon Briend, Nicolas Broutin and Gábor Lugosi.
• Random Structures & Algorithms, July 2025.

In this note, we analyze the performance of a simple root-finding algorithm in uniform attachment trees. The leaf-stripping algorithm recursively removes all leaves of the tree for a carefully chosen number of rounds. We show that, with probability 1 − 𝜀, the set of remaining vertices contains the root and has a size only depending on 𝜀 but not on the size of the tree.