A perfect n-ary tree (a.k.a. a full tree) is a tree where all of its nodes with the exception of external nodes have exactly n children.
For a binary tree, n = 2. In a perfect binary tree, the number of nodes at each height is given by 2ʰ, where h is the height of the tree. For example, at height 0 (the root), the number of nodes is 2⁰ = 1. From this knowledge, is it possible to get the total number of nodes in the whole tree?
One way is to sum up all the nodes at each level of the tree:
Factor out nʰ :
Use the geometric sum formula:
After summing:
Simplifying the previous expression results in the following total number of nodes for an n-ary tree:
and for a binary tree, n = 2:
