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

4 Answers 4

4

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?

  • 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.2012-10-25
1

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

0

For a full / complete binary tree of λ height,

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

-1

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].
  • 0
    "AFAIK for full binary tree nodes = 2^h+1 (fixed) " is wrong ..it will be $2^{h+1}-1$2018-07-27