2

Consider the following definition of a complete k-ary tree from the CLRS book:

Definition: A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k. (p.1179)

Because of this definition I consider the next binary tree as complete

CLRS Completed Binary Tree

But based on this answer definition of a complete tree (complete binary tree, a particular case of a k-ary tree),

A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

which is the same that appears on Grimaldi's discrete mathematics book (p. 601) we have that the rooted tree below is a completed tree

Completed Binary Tree

but this would not be true for CLRS definition because G leave it is not on the same level as the other ones. Which of both definitions is the most used and appropiate for the case?

Community
  • 1
  • 1
mayhem9891
  • 21
  • 1

2 Answers2

1

It depends on the use case.

The reference cited by the answer you mention ends with this qualification:

Some authors call perfect binary trees "complete".

which is indeed the usage in CLRS. So both terms are useful, but the usage varies from reference to reference.

This is why maths papers usually start with a couple of pages of terminology, even though it sometimes seems redundant.

rici
  • 234,347
  • 28
  • 237
  • 341
0

It's normally useful to use the latter definition

A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

This is primarily because of the limitations of the former definition in that you cannot have a complete k-ary tree of an size

42shadow42
  • 405
  • 2
  • 9
  • Basically what you're saying is that because it is difficult to have all the leaves on the same level I won't be able to find a complete k-ary tree? – mayhem9891 May 05 '16 at 00:16