On the Centroid of Recursive Trees
by
J.W. Moon
University of Alberta

A node v of a tree T with n nodes is a centroid node if the largest branch of the tree attached to v has at most n/2 nodes. Every tree T has either one centroid node or two (adjacent) centroid nodes. A tree T with n labelled nodes, rooted at node 1, is a recursive tree if n=1 or n>1 and T is obtained by joining node n to one of the nodes of a recursive tree with n-1 nodes; there are (n-1)! recursive trees with n labelled nodes. Our object here is to obtain certain results on the centroid node of a recursive tree. In particular, it follows from our results that as n tends to infinity the expected distance between the root and the (nearer) centroid node of a recursive tree with n nodes tends to 1; and the expected value of the label assigned to this (nearer) centroid node tends to 5/2.

Date received: November 3, 2000