GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
53 views

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 2h 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 ?

asked in DS by Active (2.2k points)   | 53 views

2 Answers

+1 vote
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..."
answered by Loyal (3.8k points)  
0 votes
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.
answered by (11 points)  

Related questions

0 votes
0 answers
2
+1 vote
2 answers
3


Top Users Sep 2017
  1. Habibkhan

    7828 Points

  2. Warrior

    2746 Points

  3. rishu_darkshadow

    2692 Points

  4. Arjun

    2672 Points

  5. A_i_$_h

    2426 Points

  6. nikunj

    1980 Points

  7. manu00x

    1920 Points

  8. Bikram

    1854 Points

  9. makhdoom ghaya

    1770 Points

  10. SiddharthMahapatra

    1718 Points


26,239 questions
33,805 answers
80,214 comments
31,159 users