# Number of 1 child nodes in a binary tree

Does anybody know how would I approach calculating the maximum number of 1 child nodes (nodes that have exactly 1 child) in a binary tree with n nodes. Please don't give me the actual answer as this is one of the homework problems, I would like to solve it by myself, but I simply don't know where to start. Any help is apreciated.

• Maximum over what? There is obviously no maximum over all binary trees. Maximum over the trees of a given depth? Maximum over the trees of a given size? Oct 4, 2013 at 23:58
• Maximum number of 1 child nodes in a binary tree with n nodes. Oct 4, 2013 at 23:59
• What about considering a tree that is a path. Oct 5, 2013 at 8:47

So in a tree with $n$ nodes, you can arrange for all but one to have a single child. This means the maximum is at least $n-1$, and of course it's at most $n$. Finally, prove that the maximum isn't $n$: there has to be at least one leaf (0-child node).
I think the maximum over trees of a given depth is a little more interesting. What's the maximum number of 1-child nodes you can cram in a binary tree of depth $n$?
For depth $0$, there's a single leaf, so the maximum is $0$. For depth $1$, enumeration shows that the maximum is $1$. More generally, what tree shape maximizes the number of one-child nodes?