In the broadcasting problem on trees, a \(\{-1,1\}\) -message originating in an unknown node is passed along the tree with a certain error probability q. The goal is to estimate the original message without knowing the order in which the nodes were informed. We show a connection to random walks with memory effects and use this to develop a novel approach to analyze the majority estimator on random recursive trees. With this powerful approach, and a Pólya urn representation, we study the entire group of very simple increasing trees as well as shape exchangeable trees together. This also extends Addario-Berry et al. [8] who investigated this estimator for uniform and linear preferential attachment random recursive trees.
