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.
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 nodesN
isN = 2^{h+1} - 1
Why? Because the first level has
2^0
nodes, the second level has2^1
nodes, and, in general, thek
th level has2^{k-1}
nodes. Adding these up for a total ofh+1
levels (so heighth
) givesThe total number of leaves
L
is just the number of nodes at the last level, soL = 2^h
. Therefore, by substitution, we getFor a
k
-ary tree, nothing changes but the2
. Soand so a bit of algebra can take you the final step to get
For any k-ary tree the total number of nodes n = [(k^(h+1))-1]/(h-1) where h is the height of the k-ary tree.
Ex:- For complete binary tree(k=2) total no. of nodes = [(2^(h+1))-1]/(h-1).
So for height 3 the total no. of nodes will be 15.
For complete ternary tree tree(k=3) total no. of nodes = [(3^(h+1))-1]/(h-1).
So for height 3 the total no. of nodes will be 40.
The formula for 2L-1 that you mentioned comes from looking on a full, complete and balanced binary tree: on the last level you have 2^h leafs, and on the other levels: 1+2+4+....+2^(h-1) = 2^h -1 leafs. When you "mess" levels in the tree and create an unbalanced one, then the number of internal nodes that you have doesn't change.
In 3-ary tree its the same logic: on the last level you have 3^h leafs, and on the other levels: 1+3+9+....+3^(h-1)= (3^h -1 )/2, that means that on a 3-ary tree you have 1.5*L - 0.5 leafs (and this make sence- because the degree is larger you need less internal nodes). I thing that also here, when you mess up levels in the tree you will still need the same number of internal nodes.
Hope that it helps you