What is exactly the definition of a complete binary tree?

[Eus]

Hi Ho! ^_^

Actually, what is the definition of a complete binary tree?
I have searched the Internet and come up with several definition. This problem is confusing enough.

According to http://planetmath.org/encyclopedia/CompleteBinaryTree.html ,
"A complete binary tree is a binary tree with the additional property that every node must have exactly two children if an internal node, and zero children if a leaf node."

Moreover, in http://www.nist.gov/dads/HTML/completeBinaryTree.html,
"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."

Furthermore, my lecture note says,
"A Complete Binary Tree is a Binary Tree with leaves on either a single level or on two adjacent levels such that the leaves on the bottommost level are placed as far left as possible"

Well, I don't know where I can find the right definition of a complete binary tree. Could you please help me?

Any help would be appreciated ^^
Thank you very much! ^^v

 

[honestrosewater]

I didn't know what a binary tree was until I saw this post, but I looked through some books on Amazon, and even they give (substantially) different definitions. I also checked several sites, and there is most agreement on:
1) All nodes of the deepest level being as far left as possible.
2) All levels except possibly the deepest being completely filled (having the maximum number of nodes).
What isn't clear is whether every internal node must have exactly two branches (or children).

Theorem. A complete binary tree of height h > 0 contains at least 2^h and at most 2^h+1 - 1 nodes.
-http://www.brpreiss.com/books/opus4/html/page355.html

I found this theorem elsewhere. Of course, I also found a problem:

Prove the following statement using mathematical induction: A complete binary tree of height h has 2^{h+1} - 1 nodes.
-source

I also found this elsewhere. The point of finding them was that 1) if every internal node must have exactly two branches, then the total number of nodes would always be odd (perhaps with the empty node or node that's just the root as exceptions). So if the total number of nodes can be even, then the internal nodes (on the second deepest level) don't need to have exactly two branches. 2) To show why I think the "right" definition is whichever definition you use. 3) Eh, it was interesting to learn about.
Maybe there's more consensus then there seems to be and someone who knows the subject better can let you know what it is. But if no one else replies, I would go with the definition that best suits your problem or try to find out from your book, problem, or teacher if you're expected to use a certain definition. Good luck.

 

[neurocomp2003]

a complete binary tree is complete on all levels except maybe the last in which case the nodes must be to the left...always go to mathworld.com to check for definitions. That is to say that its filled up on everylevel.
NOTE in mathematics that is the worst definition possible but in lamens its the easiest explanation to understand

x
x x
x x x x
x x x x

the last 2 definitions imply this though through strange wording
The Lecture Notes: what its saying is that the leaves can be on the 2nd lowest level
but all the leaves on the bottom must be towards the left as the diagram above.
Really weird wording
the Nist def'n" is basically what I said with math terms.

The Planet def'n i belivee is wrong

 

[AKG]

If you go to the NIST website and look up "full binary tree" you'll get the definition given by PlanteMath for "complete binary tree." As far as I know, there is indeed some ambiguity here. It is possible to see in texts "full" and "complete" using the definition that is given to the other term by NIST. It is also possible to see a source defining "complete" as NIST defines "full" (as in the previous case) but does not define "full" at all (not as in the previous case), as does PlanetMath.

 

[Eus]

Thank you very much for the information, guys! ^_^

Hi Ho! ^_^

Thank you very much for your precious information, guys! ^_^
I really appreciate them! ^^v

See you later, guys! ^_^