Complete Binary Tree

The article talks about complete binary tree, its properties, applications, and how to create a complete binary tree.

A Binary tree is a data structure that has a maximum of two child nodes, either it will have two, one, or zero child, but not more than two; and a binary search tree is a data structure whose left child is smaller than parent element and right child is greater than root element. The tree is used to store data in such a way that data storage and retrieval becomes easier, quicker, and more efficient. A binary tree is of various types like a full, complete, binary, and search tree. 

Also explore: All You Need to Know About Algorithms and Data Structures

A full binary tree is such a binary tree whose all nodes have either zero or two child, meaning a tree with one child node will not be considered a full binary tree. 

A complete binary tree is a tree whose all levels are completely filled except the last or lowest level, it may have one node. The complete binary tree is specifically filled from the left side.

So here in this article, we are going to discuss the complete binary tree, what precisely a complete binary tree is, some important terminologies, properties of a complete binary tree, how it is different from a full binary tree, how to create a complete binary tree, applications of a full binary tree. 

What is a Complete binary tree?

A complete binary tree is a special kind of binary tree whose all levels are completely filled except the last level, it might have one node which is strictly needed to be filled from the left side of the tree. 

Some important terms related to the Complete binary tree:

Root node: The root node does not have any parent node or any edge coming towards it. 

Child node: The node having some incoming edge.

Sibling: Two or more nodes having the same parent node. 

Internal/External node: Non-leaf nodes are internal and leaf nodes are external nodes. 

Degree: A degree of any node is calculated by counting the number of child nodes of that particular node.  

Level: Number of nodes in the path from that node to the root node. 

Height: Total number of edges from that node to the root node. 

Related – Tree Traversal in Data Structure

Properties of Complete Binary tree:

• All the levels have either zero or two nodes except the last level. 
• The total number of nodes at depth d is 2^d.
• The tree’s height with n number of nodes is log (n+1).
• The number of nodes with height h is 2^ (h+1)
• It is a proper binary tree where all the leaves have the same depth. 

Also explore: Understanding Data Structures in C: Types And Operations

How to Create a Complete Binary tree?

In a complete binary tree, each level “l” have either zero or two child except the last level of the tree, which has “2l” nodes, and all the tree is first filled from the left side. This can be represented using an array. If a parent node is at the “i” location, then it’s left child will be located at “2i + 1” location, whereas the right child is supposed to be at “2i + 2”. 

Example:

In the above example, the root node is 6 at location i = 0. 

It’s left node is at 2i + 1 = 2 * 0 + 1 = 1, so it’s left node is at location 1, which is 2. 

It’s right node is at 2i + 2 = 2 * 0 + 2 = 2, so it’s left node is at location 2, which is 7. 

Similarly, 7 is at location i = 2, 

It’s left node is at 2i + 1 = 2 * 2 + 1 = 5, so its left node is at location 5, which is 4. 

It’s right node is at 2i + 2 = 2 * 2 + 2 = 6, so its left node is at location 6, which is unavailable, so it will return Null. 

A queue data structure is used to keep track of the inserted nodes. To create a complete binary tree, we must follow the following steps:

Algorithm:

1. If the tree is empty, initialize the new node. 
2. If the tree has some elements, then take the front element of the queue:
   1. If the front element from the queue has a left child, then set the left child as the new node. 
   2. Else if the right child is not present, set it as the new node. 
3. If the front element has both right and left nodes, remove it from the queue. 
4. Now, enqueue the new data. 

Also Read – Splitting in Decision Tree

Difference between a Full binary tree and a Complete Binary tree

A complete binary tree is almost similar to a full binary tree just with only two differences:

• All the leaf elements should lean towards the left side. 
• The last leaf node might not have the right sibling or the last level may not have all the elements. 

Here is a simple illustration to understand what a full and complete binary tree looks like. 

CASE I:

The above tree is neither a complete or a full binary tree. Because all nodes do not have two or zero child, it’s not a full binary tree. Also, the elements are not lean toward the left side. Therefore, it is not a complete binary tree.

CASE II:

The above tree is a Complete Binary tree but not a Full binary tree. The above tree does not have two or zero child, so it’s not a full binary tree. But all the elements are lean toward the left. 

CASE III: 

The above tree is a full binary tree but not a complete binary tree, as all the nodes have either zero or two nodes, but all the elements are not left aligned. 

CASE IV:

The above tree is a full binary tree as well as a complete binary tree.

Application of Complete Binary Tree:

1. Heap Sort
2. All the heap sort-based data structure

Contributed by – Kanika Joshi