1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Gilles Oct 4 '13 at 23:58
  • $\begingroup$ Maximum number of 1 child nodes in a binary tree with n nodes. $\endgroup$ – flashburn Oct 4 '13 at 23:59
  • $\begingroup$ What about considering a tree that is a path. $\endgroup$ – A.Schulz Oct 5 '13 at 8:47
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks. I think I was overthinking it. Once I asked a question I managed to figure it out. Thanks for the help. $\endgroup$ – flashburn Oct 5 '13 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.