0
$\begingroup$

I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I'm not really sure how to do so. Any ideas?

UPDATE

Well I made somewhat of a progress but I also got a somewhat different result, here's what I did:

Let $T$ be an almost complete tree of height $h$ meaning that in the level of height $h$ there should be at least 1 node. Considering the fact that every height has double the number of nodes of the previous level we can derive that $T$ has the least possible number of nodes in the case that at $h$-level there is only one node. (1)

In that case the number of leaf nodes is

$l=2^{h-1}-1+1 \Rightarrow l=2^{h-1}$ and the number of total nodes is

$n=2^{h-1}-1+1$

$\Rightarrow l=2^{h-1}=\frac{2(2^{h-1}+1)}{2}=\frac{n+1}{2}$

$\xrightarrow{(1)(2)} l \geq\frac{n+1}{2}$

Now, I'm getting a bit closer but not really there yet. First problem is that I got $l \geq \frac{n+1}{2}$ and not $l \geq \frac{n}{2}$ which from what I understand stands only in the specific case that $h=1$. Second problem is that this doesn't seem like a formal proof... Any tips/suggestions?

$\endgroup$
3
  • $\begingroup$ Hint, try proving the stronger claim that there are $\lceil n/2\rceil$ leaf nodes. $\endgroup$
    – John L.
    Feb 8 '20 at 16:40
  • $\begingroup$ Hey thanks for the comment, but I couldn't really see how it could help me. Anyway I updated my post so maybe you can check if I'm getting closer, thnks again $\endgroup$
    – SlimJim
    Feb 8 '20 at 21:33
  • $\begingroup$ You are almost there, although there are a few typos in your calculation. If you have shown $l\ge \frac{n+1}2$, then you have shown $l\ge\frac n2$. To go further, you can suppose there are $x$ nodes in the level of height $h$, where $1\le x\le2^h$ $\endgroup$
    – John L.
    Feb 9 '20 at 2:38
1
$\begingroup$

According to this Wikipedia page:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree...

So, you are talking about a binary tree with $h$ levels, for which all levels with numbers $k \in [0,h-1]$ are completely filled up (i.e. have $2^k$ nodes), and the level $h$ is potentially incomplete - it contains $(2^h-r)$ nodes, where $r \in [0, 2^h-1]$ is the number of (rightmost) removed nodes. Total number of nodes of such tree is $(2^{h+1}-r-1)$. Let's find the number of leaves for this tree.

If $r$ is even, then the removal of $r$ nodes on the level $h$ will give you $\frac{r}{2}$ new leaves. So, the total number $l_{even}$ of leaves will be:

$$l_{even}=2^h - r + \frac{r}{2} = 2^h - \frac{r}{2}$$

if $r$ is odd, then the removal of $r$ nodes on the level $h$ will give you $\frac{r+1}{2}$ new leaves. So, the total number $l_{odd}$ of leaves will be:

$$l_{odd}=2^h-r+\frac{r+1}{2}=2^h-\frac{r-1}{2}$$

Now you'll be able to verify, that in both cases:

$$l \ge \frac{2^{h+1}-r-1}{2}$$

$\endgroup$
1
  • 1
    $\begingroup$ Pretty nice write-up. $\endgroup$
    – John L.
    Feb 11 '20 at 22:14

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.