Complete Binary Tree

Introduction to Complete Binary Tree

A binary tree is called complete binary tree when all the level of binary tree is completely filled except possibly the last level, which is filled from left side.

Difference between a complete binary tree and a full binary tree is that, in a complete binary tree all leaf nodes should lean towards left and the last nodes need not to have a right sibling.

In the above image we can see that in complete binary tree all the level except the last one is completely filled and in the last level all the nodes filled from the left side.

It is used in Heap Data Structure and Heap sorting. In Dijkstra’s algorithm that finds the shortest path where Heap Sort is implemented.

Min heap maintain the shape property , so it is a complete binary tree. The shape property of the tree ensures that all levels are fully filled, except the last one, and, if the last level is not filled completely, then fill the elements from left to right.

What is a Complete Binary Tree?

Tree is a non linear data structure. A general tree has no limitation on his children it can be more than two but this is not true in case of binary tree .

A binary tree is a tree data structure in which each node has atmost two child which are referred to as the left child and right child.

Complete Binary Tree

A complete binary tree is a type of binary tree in which all the levels are completely filled(i.e, have two children), except the possibly the deepest level. The deepest level can have nodes that can have either one left child or can be completely full.

A complete binary tree can be a full binary tree (when the deepest levels are completely full).

How a Complete Binary Tree is Created?

Complete Binary Tree is a binary Tree in which at every level l except the last level has 2l nodes and the nodes at last nodes are line up from left side.

It can be represented using array. Given parent is at index i so its left child is at 2i+1 and its right child is given by 2i+2

Algorithm

For creation of Complete Binary Tree when nodes is inserted in a tree in level order manner and it should be inserted from leftmost position.

Queue data structure is used to keep track of inserted nodes.

Steps to insert a node in a Complete Binary Tree:-

1. Initialize the root with new node if the tree is empty.

2. If the tree is not empty then get the front element of the queue

   • If the front element doesn't have left child , then set the left child as a new node
   • else if right child is not present then set the right child as the new node

3. And if the front node has both the children then dequeue it from the queue

4. Enqueue the new data

Intuition behind the Algorithm

1. The first element from left of the list is selected as root node.

2. The next element will be left child and third element will be right child of the root node.

3. The fourth and fifth element will be left and right child of the left child of root node.

4. The next element will be left child of the right child of root node.

Example of Complete Binary Tree

If a binary tree is a complete binary tree then its left and the right child’s index of any node is less than the total number of nodes for every node.

1. Check if a binary tree is a complete binary tree in Java

2. Check if a binary tree is a complete binary tree in C++

Other Methods to Check if a Binary Tree is a Complete Binary Tree or Not

Given a binary tree, check if it is a complete binary tree or not.

A binary tree is called complete binary tree when all the level of binary tree is completely filled except possibly the last level, which is filled from left side.

In other words all the nodes are as far left as possible in complete binary tree.

1. Level Order Traversal (BFS)

By modifying the level order traversal one can check if a given binary tree is complete or not. This is achieved by checking that each node is full node(having both right and left child) .

If any node is not a full node i.e having zero or only one child , then one should check the remaining nodes. The remaining nodes must not have any children .

If the remaining nodes have children then it is not a complete binary tree.

In this implementation we will use deque data structure. First we will insert the root node in deque and then we iterate over the deque until its size become 0.

In each iteration pop the front element and check if we have encountered a non-full node before and the current node is not a leaf node then tree is not a complete binary tree or if the left child is empty and right child is exist of the current node , then tree is not complete so return false.

If this two conditions are not true then check if the left child exist then enqueue it and do the same thing for the right child also.

a. Implementation of algorithm in C++

Time Complexity :- O(n)
Space Complexity :- O(n)

where n is the size of binary tree.

b. Implementation of algorithm in JAVA

Time Complexity :- O(n)
Space Complexity :- O(n)

where n is the size of binary tree.

2. Array representation of a complete binary tree

This problem can be solved by using a property of complete binary tree. In array representation, the left child and right child for any given node at index 'i' is present at '2i+1' and '2i+2' respectively.

Now, when constructing an array from the tree, the elements will be at their respective positions with respect to complete binary tree.

Thus presence of any vacant position means the tree is not complete.

Array representation of a complete binary tree

Array representation of a non-complete binary tree

a. Implementation of algorithm in C++

Time Complexity :- O(n)
Space Complexity :- O(n)

where n is the size of binary tree.

b. Implementation of algorithm in JAVA

Time Complexity :- O(n) Space Complexity :- O(n)

where n is the size of binary tree.

3. Space-optimized Way to Represent Complete Binary Tree as an Array

The above method uses extra space for the storage of boolean array. And know that in a complete binary tree, index of the child of left and right node is less than the total number of nodes for every node. The extra space can be avoided by passing the index as recursion parameter and checking for each and every node that their left and right child's index are in the correct range.

a. Implementation of algorithm in C++

Time Complexity :- O(n)
Space Complexity :- O(h) space requires for call stack .

where n is the size of binary tree and h is the height of tree.

b. Implementation of algorithm in JAVA

Time Complexity :- O(n)
Space Complexity :- O(h) space requires for call stack .

where n is the size of binary tree and h is the height of tree.

Full Binary Tree vs Complete Binary Tree

Full Binary Tree

Given binary tree can be called a full binary tree if all the nodes have two children except for the leaf nodes which shouldn't have any child.

The above tree is Full Binary Tree

Complete Binary Tree

Given binary tree can be called a complete binary tree if all the levels have both child except for the deepest nodes (which is filled from left) which can be partially or completely filled.

The above tree is Full Binary Tree

Complete binary tree and full binary tree are similar besides the following two difference:

1. The left node must be filled from left side.

2. The deepest node may not have the right sibling

Complete Binary Tree Applications

• Heap-based data structures

• Heap Sort