Almost complete binary tree

 Almost Complete Binary Tree

Almost complete binary tree is a binary tree which satisfies following conditions:

Insertion of nodes must takes place level by level and all the nodes must be left justified(i.e. from left to right).

All the levels from 1 to n-1 level(n stands for number of levels) should be completely filled without any gap.

Important point is that if a node at level h (where h = 1 to n) has a right child, then it also has a left child.

AT2

Here, ACBT stands for almost complete binary tree. In the above trees, left tree is a correct example of almost complete binary tree and right tree is an in-correct example of almost complete binary tree because at the last level, node left to node'F' is missing but according to the conditions of almost complete binary tree all nodes must be left justified.

Almost complete binary tree is a complete binary tree till n-1 level.

Almost complete binary tree is the subset of Complete binary tree(CBT), mean an almost complete binary tree will always be a complete binary tree.

AT3-1

Every formula that is applicable on complete binary tree is also applicable on almost complete binary tree.

Almost complete binary tree can be used in Heap Data Structures.

Example

Let us take an example:

       A

    / \

   B C

 / \ 

D E 

Here, above tree is a complete binary tree as well as almost complete binary tree both. Now, Lets do some operations on this tree, given below:

Lets insert a new node 'F' in the tree.

       A

    / \

   B C

 / \ /

D E F

Here, according to the definition(above-mentioned), it is an almost complete binary tree as well as complete binary tree both.

2. Lets insert one more new node 'G' in the tree.

       A

    / \

   B C

 / \ / \

D E F G

Now, tree is a complete binary tree only, but according to the conditions of almost complete binary tree(above-mentioned) it is not an almost complete binary tree.

Again if we look closly at this tree, it is also a Full binary tree.

3. Now, Lets delete a node 'F' from the tree

       A

    / \

   B C

 / \ \

D E G

Now, After the deletion of node 'F', due to the violation of the rules it doesn't satisfy the definition. Therefore, this tree is neither an almost complete binary tree nor complete binary tree