Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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
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

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|cite|improve this answer

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|cite|improve this answer

For a full / complete binary tree of λ height,

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

share|cite|improve this answer

Your Answer


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.