In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer:
$$ \sum^{h}_{i = 0}k^i $$
where h is the height and k is the max number of children
It's supposed to be "how many nodes in a full and complete k-ary tree" right? Because the definition of a complete tree is:
a binary tree T with n levels is complete if all levels except possibly the last are completely full,and the last level has all its nodes to the left side.
So the number of leaves might not be k so this formula only applies to full and complete am I right? or did I misunderstand something?
Best Answer
Yes you are correct. It should be a full and complete tree.