Complete Binary Tree

Introduction

An array can be stored in a complete binary tree without needing the help of any pointer.

Two things are kept into view while constructing data structure that is memory and time. Data structure should ensure two things:

1. Running of the programs in a fast manner.
2. It shouldn’t use a lot of memory so that a large part of memory occupied by it doesn’t go waste.

We know that we usually use pointers in binary tree. But excessive pointers make the code nasty and hard to manage it. There is a type of binary tree called complete binary tree. The good thing about this complete binary tree is that we don’t have to use the pointers for this. Because, it’s going to work perfectly fine with arrays. Yes, that’s true, we play with binary tree using arrays, but make sure it’s complete binary tree. If it’s not complete binary tree, then it’s going to be problematic for memory. We’ll discuss all these things in our following article.

What is Complete Binary Tree?

• A complete binary tree is a tree that is completely filled, with the possible exception of the bottom level.
• The bottom level is filled from left to right.

Figure-1 is showing complete binary tree. Because, the nodes are filling from left to right at the bottom.

Properties of Complete Binary Tree

Step-by-step Guide about Complete Binary Tree

Figure-3 is showing the complete binary tree and the array at the bottom, representing the nodes inside the box along the indexes at the bottom.

For any array element at position i, the left child is at 2i, the right child is at (2i + 1) and the parent is at floor (i/2).

See the following figures to understand the above statement. Node A, being at position 1, has left and right children as B and C which are at index 2(1)=2 and 2(1)+1=3 respectively. Similarly, you can also find the parent of the node. The parent of the node at position 2 or 3 is at position 2/2=1 or 3/2=1 respectively.

In the same way, you can also check for the other nodes’ position in the array.

There are some situations where the use of pointers is beneficial. The balancing of AVL tree is an example in this regard. Here pointers are more efficient. If we’re using array, there will be need of moving a large data here and there to balance the tree.

Problem of using Array for the Binary Tree

Make sure, the tree is complete binary tree, if you’re using array.

What if you don’t use complete binary tree, then the array would like this, shown if figure-6.

You can see, there are empty segments in the array, while the array should be continuous. This leads to the wastage of memory Due to this reason, it is thought that if a tree is not completely binary, it is not good to store it into an array. Rather, a programmer will prefer to use pointers for the storage.

REFERENCE: CS301 Handouts (page 326 to 335)