# Complete $k$-ary tree with exactly $n$ leaves

A **complete $k$-ary tree** has all _levels_, except possibly the last, completely filled.

                    - - - - [.] - - - -
                  /                     \
                 /                       \
                /                         \
               /                           \
             (*)                           (*)
           /     \                       /     \
          /       \                     /       \
         /         \                   /         \
        /           \                 /           \
      ()             ()             ()             ()
     /  \           /  \           /  \           /  \
    /    \         /    \         /    \         /    \
   *      *       *      *       *     11       12    13
  / \    / \     / \    / \     / \     
 1   2  3   4   5   6  7   8   9  10

Specifically, **levels** are numbered from $0$ to $h$, with the root being at level 0 and the _leaves_ at level $h$. A level $i\in[0,h]$ has exactly $k^i$ nodes on it.

A **leaf** is defined as a node in the tree that has 0 children.

In a complete tree, leafs can be either on level $h$ or $h+1$ or both.

## How to fit exactly $n$ leaves?

Sometimes, we want our a complete $k$-ary tree to have exactly $n$ leaves. **This is easy** when $n = k^h$ for some $h$: just create tree with $h+1$ levels, and put all leaves on level $h$. Done.

But when $k^h < n < k^{h+1}$, we are in trouble: we will need to put some of the leaves on the 2nd-to-last level $h$ and the others on the last level $h+1$.

But how do we know how to split the leaves across these levels?

### Attempt 1: Works for _some_ $n$ or for _any_ $n' = n \pm \varepsilon, \varepsilon\in[1,k-1]$

Assume the 2nd-to-last level $h$ will store $R$ leaves, which means that the last level $h+1$ *could* store exactly $L = (k^h - R)\cdot k$ leaves. (This won't work for any $n$ though, but we'll fix it.)

Overall, we would need these two levels together to store all $n$ leafs, so:
\begin{align}
n &= L + R = (k^h - R)\cdot k + R
\end{align}
Now, we can solve for $R$, to figure out how many leaves we'll put on level $h$:
\begin{align}
n &= (k^h - R)\cdot k + R\\
n &= k^{h+1} - Rk + R\\
n &= k^{h+1} - R(k - 1)\\
R &= \frac{k^{h+1} - n}{k - 1}
\end{align}
The problem we'll run into here is that the numerator might not be divisible by the numerator.

One thing we can do is change $n$ into $n' = n\pm\varepsilon,\varepsilon\in[1,k-1]$, which will be divisible for some $\varepsilon$ guaranteed.

That's _hacky though_.

### Attempt 2: Works for _almost every_ $n$

We'll instead allow level $h+1$ to store $L = (k^h - R - 1)\cdot k + \varepsilon$ leaves, by having the level $h$ parent of the last leaf from level $h+1$ have $1 \le \varepsilon \le k$ children.

The new formula for $n$ becomes:
\begin{align}
n &= (k^h - R - 1)\cdot k + R + \varepsilon\\
n &= k^{h+1} - Rk + R - k + \varepsilon\\
n &= k^{h+1} - R(k - 1) - k + \varepsilon\\
R &= \frac{k^{h+1} - n - (k-\varepsilon)}{k - 1},\text{for}\ 1 \le \varepsilon \le k
\end{align}

So, all we need to do is find the $(k-\varepsilon) \in [0,k-1]$ for which the numerator is divisible.

Unfortunately, this will never allow for the case where $R = 0$ and $L = n$. For example, consider $n=3$ in a binary tree: all three leaves go on the last level, with the last leaf's parent having only two children:

       *
     /   \
    /     \
   *       *
  / \     /
 1   2   3

In other words, our formulas above implicitly assume that $R > 0$.

### Attempt 3: Works for _every_ $n$

We can deal with the problematic case above by identifying it via:
$$k^{h+1} - n < k$$

If so, we let $L = n$ and $R = 0$. Otherwise, we use the formula from _"Attempt \#2."_