Example & Tutorial understanding programming in easy ways.

What is complete binary tree?

Definition :
A binary tree in which every level (depth), except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

A complete binary tree has 2k nodes at every depth k < n and between 2^n and 2^(n+1)-1 nodes altogether. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with 1-based indexing. If child index is greater than the number of nodes, the child does not exist.

Difference between Binary tree and Complete Binary Tree :
In Binary Tree, it may be possible that some node have their right subtree or right node without left node.
But in Complete Binary tree Left node is first priority to fill then right Node fill.




Read More →