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

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?

• Hint, try proving the stronger claim that there are $\lceil n/2\rceil$ leaf nodes. Feb 8, 2020 at 16:40
• 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 Feb 8, 2020 at 21:33
• 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$ Feb 9, 2020 at 2:38

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

• Pretty nice write-up. Feb 11, 2020 at 22:14