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^{\prime }=n\pm \epsilon ,\epsilon \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{array}{rl}n& =L+R=(k^h-R)\cdot k+R\end{array}$$
Now, we can solve for

$R$, to figure out how many leaves we'll put on level

$h$:

$$\begin{array}{rl}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{array}$$
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^{\prime }=n\pm \epsilon ,\epsilon \in [1,k-1]$, which will be divisible for some

$\epsilon$ 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+\epsilon$ leaves, by having the level

$h$ parent of the last leaf from level

$h+1$ have

$1\le \epsilon \le k$ children.

The new formula for

$n$ becomes:

$$\begin{array}{rl}n& =(k^h-R-1)\cdot k+R+\epsilon \\ n& =k^{h+1}-Rk+R-k+\epsilon \\ n& =k^{h+1}-R(k-1)-k+\epsilon \\ R& =\frac{k^{h+1}-n-(k-\epsilon )}{k-1},\text{for}1\le \epsilon \le k\end{array}$$

So, all we need to do is find the

$(k-\epsilon )\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."