Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If the level ($\lambda$) of a full binary tree at zero is just a root node, than I know that I can get the maximum possible number of nodes (N) for a full binary tree using the following:

N = $2^{\lambda+1}$- 1

Is the minimum possible number of nodes the following?

N = 2*$\lambda$ + 1

share|improve this question
add comment

3 Answers

For a full binary tree $T$ of height $\lambda$, I believe that the maximum number of nodes is $N = 2^{\lambda + 1} - 1$ (not $+1$.)

It seems likely that you can prove the minimum number of nodes for a full binary tree of height $\lambda$ inductively. (We can readily verify that the minimum number of nodes for $\lambda = 1$ is $2\times 1 + 1 = 3$, showing the base case to be true.) Assuming (inductively) that for $\lambda = k$ we have a minimum of $N = 2k+1$ nodes, if we add a node, it must branch from one of the leaves. But in order to maintain a full binary tree, we must add an additional node; that is, adding an additional levels requires at minimum two more nodes. So, we will have $N+2$ nodes. Then, by our induction hypothesis $N+2 = (2k+1) + 2 = 2(k+1) + 1$, which is what we wanted.

Not exactly formal, but does that make sense?

share|improve this answer
    
whoops that is a typo, it should have been - 1 instead of + 1, I will fix it. –  5StringRyan Oct 24 '12 at 23:31
1  
You might as well start your induction at $\lambda=0$: the result is true for height $0$. Your argument shows that the minimum must be at least $2\lambda+1$; to show that it actually is $2\lambda+1$, you must show that for each $\lambda$ there is a full binary tree of height $\lambda$ with $2\lambda+1$ nodes. One way: let $T_\lambda$ be the set of binary sequences of length $\le\lambda$ such that at most the last bit is $1$; if $s,t\in T_\lambda$, $s\le t$ iff $s$ is an initial segment of $t$. The empty string is the root. This is a full binary tree with $2\lambda+1$ nodes. –  Brian M. Scott Oct 25 '12 at 11:17
add comment

if I is the number of internal nodes, then total number of nodes is 2I+1 according to Full Binary Tree Theorem. You could try proving that the number of internal nodes I is equal to the number of levels, $\lambda$, but from an example

:
enter image description here

We see that it is not true in every case. (I = 3, $\lambda = 4$). However, it seems to be true that $I = \lambda -1$, from which you could get a strict number of nods $2\lambda -1$.

share|improve this answer
add comment

Sorry to say but what all of you are discussing. AFAIK for full binary tree nodes = 2^h+1 (fixed).

  • For strict binary tree, max node = 2^h+1 and min node= 2h+1.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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