Data Structures and Algorithms - Old Questions

7. Explain almost complete binary tree with example.

A almost complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position.

A binary tree is a almost complete binary tree (of height h , we take root node as 0 ) if and only if :-

• Level 0 to h-1 represent a full binary tree of height h-1
• One or more nodes in level h-1 may have  0, or 1 child nodes

• If F, G are nodes in level h-1, then F has  more child nodes than G if and only if F is to the left of G , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

Example:

Fig: almost complete binary tree