GATE CSE
First time here? Checkout the FAQ!
x
0 votes
36 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 Junior (823 points)   | 36 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 (3k 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)  


Top Users Jul 2017
  1. Bikram

    4894 Points

  2. manu00x

    2888 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1496 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. Arnab Bhadra

    1114 Points

  9. pawan kumarln

    1114 Points

  10. Ahwan

    940 Points


24,089 questions
31,062 answers
70,677 comments
29,400 users