Problem Detail: 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.
Asked By : flashburn
Answered By : Gilles
Try to construct a tree with a lot of 1-child nodes. Start with the root. Let’s say the root has exactly one child. Let’s say that that child itself has exactly one child, etc.
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?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14817
