  We study the broadcasting problem when the underlying tree is a random
recursive tree. The root of the tree has a random bit value assigned. Every
other vertex has the same bit value as its parent with probability $1-q$ and
the opposite value with probability $q$, where $q \in [0,1]$. The broadcasting
problem consists in estimating the value of the root bit upon observing the
unlabeled tree, together with the bit value associated with every vertex. In a
more difficult version of the problem, the unlabeled tree is observed but only
the bit values of the leaves are observed. When the underlying tree is a
uniform random recursive tree, in both variants of the problem we characterize
the values of $q$ for which the optimal reconstruction method has a probability
of error bounded away from $1/2$. We also show that the probability of error is
bounded by a constant times $q$. Two simple reconstruction rules are analyzed
in detail. One of them is the simple majority vote, the other is the bit value
of the centroid of the tree. Most results are extended to linear preferential
attachment trees as well.
