math - What is the total number of nodes in a full k-ary tree, in terms of the number of leaves?

Question

I am doing a unique form of Huffman encoding, and am constructing a k-ary (in this particular case, 3-ary) tree that is full (every node will have 0 or k children), and I know how many leaves it will have before I construct it. How do I calculate the total number of nodes in the tree in terms of the number of leaves?

I know that in the case of a full binary tree (2-ary), the formula for this is 2L - 1, where L is the number of leaves. I would like to extend this principle to the case of a k-ary tree.

Answer 1

Think about how to prove the result for a full binary tree, and you'll see how to do it in general. For the full binary tree, say of height h, the number of nodes N is

N = 2^{h+1} - 1

Why? Because the first level has 2^0 nodes, the second level has 2^1 nodes, and, in general, the kth level has 2^{k-1} nodes. Adding these up for a total of h+1 levels (so height h) gives

N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1) / (2 - 1) = 2^{h+1} - 1

The total number of leaves L is just the number of nodes at the last level, so L = 2^h. Therefore, by substitution, we get

N = 2*L - 1

For a k-ary tree, nothing changes but the 2. So

N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1) / (k - 1)

L = k^h

and so a bit of algebra can take you the final step to get

N = (k*L - 1) / (k-1)