CODEWITHSUNDEEP
algorithmdata-structuresbinary-tree
user366312
user366312

Reputation: 17016

Is this a Complete Binary Tree?

enter image description here

If this is a Complete Binary Tree, why the following is not?

enter image description here

Upvotes: 4

Views: 848

Answers (2)

user1657017
user1657017

Reputation:

for reference see this http://www.youtube.com/watch?v=tORLeHHtazM

data structures by Dr. naveen garg. Both of them are not complete binary tree.Because a complete binary tree is a binary tree that has (2^i) nodes at level i.

Upvotes: 0

zw324
zw324

Reputation: 27210

See Wikipedia:

Types of binary trees

  • A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambiguously also called a complete binary tree.)
  • A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

So there is ambiguity involved. With the complete = perfect definition, these two are not complete. But with the second definition, the first is, since except for the bottom level it is perfect, and all the leaves at the bottom level are in the far left of the tree.

As a side note, wikipedia referenced NIST, and the NIST page indicates this under the perfect binary tree:

This kind of tree is called "complete" by some authors ([CLR90, page 95], Leighton) and "full" by others (Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461).

For those who does not recognize, CLR is Corman, Leiserson, Rivest, who are the authors of Introduction to Algorithms.

Then again, the second definition is used in KDE's The Art of Computer Programming (See Complete Binary Tree at Wolfram Mathworld), which is one of the few books in the area of algorithms that carries more weight than CLR.

Upvotes: 5

Related Questions