4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ whoops that is a typo, it should have been - 1 instead of + 1, I will fix it. $\endgroup$ Oct 24 '12 at 23:31
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 25 '12 at 11:17
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

For a full / complete binary tree of λ height,

Maximum nodes = 2^(λ+1)-1; Minimum nodes = 2^λ;

$\endgroup$
-1
$\begingroup$

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

  • For strict binary tree, max node = [2^h + 1] and min node = [2h + 1].
$\endgroup$
1
  • $\begingroup$ "AFAIK for full binary tree nodes = 2^h+1 (fixed) " is wrong ..it will be $2^{h+1}-1$ $\endgroup$
    – laura
    Jul 27 '18 at 10:21

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.