difference between complete and almost complete binary tree

Question

A complete tree is a tree in which every level is completely filled and an Almost complete tree is a tree in which if last level is not completely filled then all nodes are as far as left as possible. my confusion is in following example of binary tree:

            O
          /   \
         O      O
       /  \    / \
      O    O  O   O
     / \
    O   O

According to definition it should be an incomplete binary tree but it is a complete binary tree. if someone could elaborate how is this complete binary tree and why not an incomplete binary tree?

Answer 1

Your example is a complete binary tree: a complete binary tree can have an incomplete last level, as long as all the leaves in it are pushed across to the left.

A perfect binary tree is a complete binary tree in which the last level is full.

An almost complete binary tree is a complete but not perfect binary tree. So your example is also almost complete.

The terminology is confusing, but an almost complete binary tree is also complete.

Answer 2

Not sure where some of these terms are coming from... the technical terminology for binary trees that I've learned are strictly binary, complete, and almost complete.

Strictly binary trees are binary trees where every node either has two children or is a leaf (has no children).

Complete binary trees are strictly binary trees where every leaf is on the same "maximum" level.

Almost complete binary trees are not necessarily strictly binary (although they can be), and are not complete. If the tree has a maximum level of d, then the subtree containing all the nodes from the root to level d-1 is a complete tree. Additionally, if a node has a right descendant at level d, then its left subtree is a complete tree whose leaves are all at level d (all the "bottom" nodes of the tree are "as far left as possible").

From what I've been taught, the accepted answer would be incorrect in saying that "an almost complete binary tree is also complete." They're not. An almost complete binary tree would be complete if you removed every leaf at the tree's lowest level.

Answer 3

Actually, the confusion arises due to reading from different books. The explanation of complete binary tree (i.e. every level except possibly the last, is completely filled and all nodes are as far left as possible) is in some books referred as almost complete binary tree and explanation of FBT takes as explanation of CBT and explanation of strictly BT takes as FBT. They don't have any explanation of strictly binary tree or if it possible they don't have explanation for FBT.

Answer 4

You're confusing things. Where did you get those definitions?

definitions:

a binary tree T is full if each node is either a leaf or possesses exactly two child nodes.

and

a binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

Your interpretation of "complete tree" seems to be what is referred as "full & complete tree"

Source: http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf

Answer 5

An ACBT is a tree in which each node that has a right child also has a left child . Having a left child does not necessarily require a node to have a right child.

Answer 6

I like the following definitions.

Complete binary tree:

In a complete binary tree, all the levels of a tree are filled entirely except the last level. In the last level, nodes might or might not be filled fully. Also, let’s note that all the nodes should be filled from the left.

Almost complete binary tree:

An almost complete binary tree is a special kind of binary tree where insertion takes place level by level and from left to right order at each level and the last level is not filled fully always

So an almost complete binary tree is also a complete binary tree. The difference with a complete BT is that almost complete BT has the last level is not filled fully always.

Source: https://www.baeldung.com/cs/complete-vs-almost-complete-binary-tree