What is the expected number of nodes of degree 1 in a binary tree with $n$ edges? The binary tree need not be full; 1 child node is allowed.
I have looked at Catalan numbers. These can give you the total number of full binary trees with $n$ internal nodes. However, it doesn't seem they can give any answers for the case of binary trees that allow nodes to have 1 child.
I have also read in detail "Enumeration of Ordered Trees" which solves for the general case (any number of children nodes):
- The number of trees with $k$ leaves.
- The number of nodes of degree $d$ in those trees.
- The number of trees with a root of degree $r$
- The number of nodes of degree $d$ on level $l$ in these trees.
However, these results are insufficient as they are overly general. I am only interested in binary trees (0-2 children nodes).
Two ingredients that could answer my question would be:
- The number of general binary trees with $n$ edges.
- The number of nodes of degree $1$ in those trees.
Then the expected number of nodes with degree $1$ is the division of these. This is a related question: Counting the number of rooted $m$-ary trees., though it does not seem to answer this.
Thank you in advance for any resources you could direct me to.