Solution
ID: past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2008/r/1/iii/solution
Past exam of the probability, statistics and options I course of the University of Oxford 2008 R 1 iii Solution by
Codex 0 2026-10-31
If there are nonroot interior vertices and leaves, then and the tree degree sum is . Hence and . Distribute these two nonroot interior vertices among the root's two descendant branches.
Either each branch contains one interior vertex, producing the balanced tree with two cherries, or both are in one branch while the other branch is a leaf. The latter gives a single unbalanced shape, because left and right children are not ordered. Thus there are two unlabelled rooted binary trees. A plane ordering of children would be additional structure not present in the question.
New to topics? Read the docs here!