For any odd positive integer $n$, there is a recursive binary tree that has depth at most $\log_2(n)$ - why?

39 Views Asked by At

In chapter 7 of "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018), I have a doubt concerning a theorem about binary trees.

Relevant definitions

Before going into the specific doubt, here are some definitions (adapted from the book) that I thought would be relevant.

Definition 1. $\text{BBTr}$ is the set of binary branching trees.

Definition 2. $\text{Leaves}$ is the set of leaves: $\text{Leaves} := \{ T\in \text{BBTr | }T\text{ is a leaf} \}$.

Definition 3. $\text{Branching}$ is the set of non-leaf trees: $\text{Branching} := \text{BBTr} - \text{Leaves}$.

Definition 4. $\text{left}$ and $\text{right}$ are selector functions that produce the left and right branches of non-leaf elements of $\text{BBTr}$. The left branch of $T$ is the tree $\text{left}(T)$ and the right branch is $\text{right}(T)$.

Definition 5. The set $\text{RecTr}$ of recursive trees is defined recursively. For $T\in \text{BBTr}$:

Base case: ($T\in \text{Leaves}$). $T\in \text{RecTr}$.

Constructor case: ($T\in \text{Branching}$). If $\text{left}(T)$, $\text{right}(T)\in \text{RecTr}$, and these two trees have no subtree in common, then $T$ is in $\text{RecTr}$.

Definition 7. The size of a tree $T\in \text{BBTr}$ is the number of subtrees it has.

Definition 8. The depth of a recursive tree $T$ is the length of its longest path starting from the root node $T$.

Doubt

By doubt concerns the following theorem and corollary about binary trees:

Theorem. If $B\in \text{RecTr}$ is fully balanced with depth at least one, then $\text{size}(B) \geq 2^{\text{depth}(B)} + 1$.

Proof. The smallest fully balanced tree with depth $d \geq 1$ will be a complete tree of depth $d - 1$ along with two leaves of depth $d$, so its size will be $(2^d - 1) + 2 = 2^d + 1$.

Corollary. For any odd positive integer $n$, there is a recursive binary tree - namely, a fully balanced tree of size $n$ - that has depth at most $\log_2(n)$.

I understand the reasoning of the theorem and its proof, but I can't seem to understand how this corollary follows from the theorem.

Taking the (base-2) $\log$ of both sides of $\text{size}(B) \geq 2^{\text{depth}(B)} + 1$:

$size(B) \geq 2^{\text{depth}(B)} + 1 \geq 2^{\text{depth}(B)}$

$\log (\text{size}(B)) \geq \text{depth}(B)$

$\text{depth}(B) \leq \log (\text{size}(B))$

For a tree of size $n$, the result above seems to match the part of the corollary that says: "has depth at most $\log_2(n)$". However, I don't see why the corollary says "For any odd positive integer $n$". In particular, I don't get why $n$ has to be odd.

What am I missing?