Almost complete Binary Tree

A complete Binary tree of height h has 2^h-1 nodes. Out of these 2^h-1 nodes (almost half nodes) are leaf nodes and rest (2^h-1-1 are non-leaf nodes).

Read more about complete binary trees here or watch video. Below are all complete binary trees:        

All Leaf nodes of complete binary tree are at same level. There is no hole in a complete binary tree (no missing nodes between two nodes of a level). It has maximum number of nodes possible for any binary tree of a particular height.

In complete binary tree, there will never be a node that has only one child. All non-leaf nodes will have both the children. None of the below trees is complete binary tree:

Canonical labeling of nodes

Label the Nodes in the level-wise fashion from left to right, as shown below:

The advantage of canonical labeling is that such a tree can be stored in an array where value of a node is stored at the index equal to its label in the tree.

This way we will save a lot of memory because we do not need to store all the pointers. If you have noticed, there is a relationship between the labels of a node and its children above:

This way, it becomes easy to move in either upward or downward direction of a tree, even when it is stored in an array.

Almost Complete Binary Tree

A the binary tree made up of the first n nodes of a canonically labeled complete Binary Tree is called Almost complete Binary Tree. Below are all almost complete binary trees,

Below trees are NOT almost complete binary trees (the labeling has no meaning, because there are gaps).

As seen above an almost complete binary tree can be stored in an array.

Every almost complete binary tree is also 'Complete Binary tree' but the Vice-Versa may not be true.

We have earlier written code to check is a given tree is an Almost complete binary tree or not.