0
$\begingroup$

Is it possible to be able to count the number of leafs in a perfect binary tree where the number of nodes is not given?

I wanted to use the formula $2l-1$ in my proof for how many nodes are in a perfect binary tree but for $l$, I am not sure how to find this value before showing $2l-1$ is the number of nodes.

Should I use induction and rely on the base cases and inductive hypothesis to prove the formula holds instead of trying to find an explicit formula for $l$?

$\endgroup$
  • 4
    $\begingroup$ Let's take a concrete example: I'm thinking of a perfect binary tree. Can you tell me how many leaves it has? Because if the answer is "no", then we're done. If it's "yes", you've done something amazing (or lucky). Most likely, you actually know something else about the binary tree in your problem (for instance, you might know its depth, and that it's complete) ... but unless you tell us what other information you're given, we're in the same position you are as you try to guess the number of nodes in the tree I'm thinking about. $\endgroup$ – John Hughes Oct 22 '18 at 17:04
  • $\begingroup$ @JohnHughes Hello, thank you for taking the time to respond. I did figure out what the depth is for the given tree. The depth (longest path from root to leaf) is $2^{n+1}-1$ where $n$ is the index of a recursively defined binary tree. So if I do know the depth of each binary tree, how do I deduce the number of leafs? For the kind of binary tree it is, I don't think it is complete because each node has two children, no more or less. $\endgroup$ – numericalorange Oct 22 '18 at 17:18
2
$\begingroup$

According to wikipedia

https://en.wikipedia.org/wiki/Binary_tree#Common_operations

For a perfect binary tree, $\ell$ (the number of leaves) is $2^h$, where $h$ is the height. (Perfect in this case means that each internal node has exactly two children, and all leaves are at the same depth. If you don't know that the "same-depth" condition is true for your tree, then your question is again unanswerable without further information.)

That formula certainly seems to check out for height $1$, where there's a root and two leaves, since $2 = 2^1$.

In your case, you say that you have $h = 2^{n+1}-1$, so the number of leaves is $$ \ell = 2^{(2^{n+1}-1)}. $$

I personally suspect that your formula for height is messed up, because $2^{n+1}-1$ happens to be the formula for the number of leaves in a tree of height $n$, but I'm gonna have to trust that you mean what you say, so I've written the answer above.

$\endgroup$
  • $\begingroup$ The first four binary trees have 1, 2, 6, 30 leafs and so 1, 3, 11, 59 nodes (2l - 1). I am trying to find a way to find the number of leafs for nth tree so I can deduce the number of nodes for that tree. The tree does not have equal depths for each leaf, for each tree the longest depth is $2^{n+1} - 1$, n being the (n-1)th tree. I am sorry if I sound confusing... Maybe induction is a good way to go about this! $\endgroup$ – numericalorange Oct 22 '18 at 17:40
  • 1
    $\begingroup$ I'm going to be harsh here and say that the best way to go about this is to have a clear understanding of the problem, state it unambiguously, and draw out three or four examples. What you've said so far is inconsistent: Trees with $1, 3, 11, 59$ nodes do not have heights $2^{0+1}-1 = 0$, $2^{1+1}-1 = 3$, $2^{2+1}-1 = 6$, and $2^{3+1}-1 = 15$, because every tree of height $3$ has at least four nodes. Until you can make only true statements about your problem, you should probably not hope to solve it. When working from false assumptions, the method --- induction or other -- doesn't matter. $\endgroup$ – John Hughes Oct 22 '18 at 17:56
  • $\begingroup$ I see what you mean. Thank you for helping me nonetheless, you helped me more than you know, despite all the confusion! $\endgroup$ – numericalorange Oct 22 '18 at 20:24
  • $\begingroup$ Glad to have been of service. And I learned something too: I felt sure that this was going to become a chameleon problem, and I was wrong; I learned that my predictive skills aren't all that great. :( $\endgroup$ – John Hughes Oct 22 '18 at 20:27

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.