Application of the Complete binary tree

What is a Complete Binary Tree?

A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible....

Some terminology of Complete Binary Tree:

Root – Node in which no edge is coming from the parent. Example -node A Child – Node having some incoming edge is called child. Example – nodes B, F are the child of A and C respectively. Sibling – Nodes having the same parent are sibling. Example- D, E are siblings as they have the same parent B. Degree of a node – Number of children of a particular parent. Example- Degree of A is 2 and Degree of C is 1. Degree of D is 0. Internal/External nodes – Leaf nodes are external nodes and non leaf nodes are internal nodes. Level – Count nodes in a path to reach a destination node. Example- Level of node D is 2 as nodes A and B form the path. Height – Number of edges to reach the destination node, Root is at height 0. Example – Height of node E is 2 as it has two edges from the root....

Properties of Complete Binary Tree:

A complete binary tree is said to be a proper binary tree where all leaves have the same depth. In a complete binary tree number of nodes at depth d is 2d.  In a  complete binary tree with n nodes height of the tree is log(n+1). All the levels except the last level are completely full....

Perfect Binary Tree vs Complete Binary Tree:

A binary tree of height ‘h’ having the maximum number of nodes is a perfect binary tree. For a given height h, the maximum number of nodes is 2h+1-1....

Full Binary Tree vs Complete Binary tree:

For a full binary tree, every node has either 2 children or 0 children....

Creation of Complete Binary Tree:

We know a complete binary tree is a tree in which except for the last level (say l)all the other level has (2l) nodes and the nodes are lined up from left to right side.It can be represented using an array. If the parent is it index i so the left child is at 2i+1 and the right child is at 2i+2....

Application of the Complete binary tree:

Heap Sort Heap sort-based data structure...