# Is this formula for the number of nodes for a complete tree or a full and complete tree?

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?

-

2
Yes you're right. – Jernej Jan 18 at 8:38

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9559992551803589, "perplexity_flag": "middle"}