# Number of nodes of a binary tree at height $i$

It is well known that at height $$i$$ the number of nodes is bounded by $$\frac{n}{2^{i+1}}$$, for example there are at most $$n/2$$ leafs.

Now, it makes sense only if we're taking $$\left\lceil \frac{n}{2}\right\rceil$$, because for example, a binary tree with $$7$$ nodes has $$4$$ leafs at most.

My question is: why do we take $$\left\lceil \frac{n}{2}\right\rceil$$ and not $$\left\lfloor \frac{n}{2}\right\rfloor$$?

Asympotically, isnt it safer to assume we have more nodes then there actually are?

• Confused by your question upon rereading. You first motivate that the ceiling function is the correct answer and then ask why the ceiling function is used. Did you mean to write about the floor function instead? Dec 15, 2021 at 19:16
• The number of nodes is not bounded by $\frac{n}{2^{i+1}}$. Simply substitute $i=\log(n)$ and you already get that there are at most $2$ nodes at this level (which is obviously wrong, there may be a lot more). The correct term that bounds this is just $2^i$: each new level may increase the number of nodes by at most two (since every node may have at most two children). Dec 15, 2021 at 20:25
• @nirshahar Actually it sounds correct that at the height $\log(n)$ there would be at most 2 nodes. Maybe your'e confusing height and depth? by height =0, for example, I mean the leafs (and your expression obviously gives wrong answer). Dec 15, 2021 at 21:10
• Oh, then that is right. If you meant that height $0$ are leaves then yes. I thought you meant that height $0$ is the root :o Dec 15, 2021 at 22:22

## 1 Answer

We use $$\lceil \frac{n}{2} \rceil$$ instead of $$\lfloor \frac{n}{2} \rfloor$$ since our task is to find an upper bound.

To understand this, lets take for example two real positive numbers $$0. In this expression, $$y$$ is an upper bound for $$x$$, but is not necessarily a whole number. However, both $$\lceil y \rceil$$ and $$\lfloor y \rfloor$$ are whole numbers. We still want to retain a similar bound, but now using $$\lceil y \rceil$$ or $$\lfloor y \rfloor$$ instead of $$y$$.

Note, that $$y\le \lceil y \rceil$$, and therefore $$x and thus $$\lceil y \rceil$$ is an upper bound.

But $$\lfloor y \rfloor \le y$$, and thus it is not necessarily true that $$x < \lfloor y \rfloor$$. For example, $$x=0.5,y=0.75$$ will be a counter-example, since $$\lfloor y \rfloor=0 < x$$.

Therefore, for correctness we must use the ceiling for upper bounds. Similarly, for lower bounds we will use the floor instead.

As a side note, asymptotically taking a ceiling is equivalent to taking a floor, since they must both be at most distance $$1$$ from each other: $$\lceil y \rceil \le \lfloor y \rfloor + 1$$.