Complete Binary tree

Question

What exactly is a Complete Binary Tree?

Different sources provide different definitions:

Source 1 :

A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d.

http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html

Source 2 :

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes at the last level h.An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed.

https://en.wikipedia.org/wiki/Binary_tree

Wiki says ::

Some authors use the term complete to refer instead to a perfect binary tree as defined above(Source2), in which case they call this type of tree an almost complete binary tree or nearly complete binary tree^.

Which definition to follow ?

Answer 1

There is no standard definition ... they will clearly mention in exam what they actually mean by saying "a complete binary tree", incase if they didnt give always take that " a complete binary tree is a binary tree with all levels full except the last level where leaves are as left as possible..."

Answer 2

The second definition is correct.A complete binary tree has all levels full except the last level, which may or may not be full, at the same time leaves in the last level are as left as possible.

Also all leaves may not be at depth d, because if last level is not full, then some nodes at depth d-1 be leaf nodes.So first definition seems a little vague.

Comments

If nothing is mentioned in the paper than this is right answer considering past GATE question.

But most often they mention what is a complete binary tree as there is ambiguity about the definition itself.