General N-ary Trees Theorems

We will now proceed to prove a number of theorems about perfect binary trees.

1) Nodes in a Perfect N-ary Tree : Theorem

2) Logarithmic Height

and therefore logN(n) is a reasonable approximation of the height of a perfect N-ary tree with n nodes.

3) N-ary Trees versus Binary Trees

The ratio of the heights of a binary tree containing n nodes and an N-ary tree containing n nodes is