Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Yes you're right. – Jernej Jan 18 '13 at 8:38
up vote 0 down vote accepted

Yes you are correct. It should be a full and complete tree.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.