Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

Question

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?

Answer 1

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