The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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.

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.

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 Loyal (3.8k points) | 80 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 Boss (5.6k 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
+1 vote
2 answers

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,981 questions
36,818 answers
34,706 users