Array Representation of Binary Tree


💡 What is Full Binary Tree?

A full binary tree is also known as a proper binary tree or a 2-tree is a tree in which every node other than the leaves has two children.

If height of the tree is h then the maximum number of nodes – 2^(h+1) – 1;

It means when a tree has a maximum number of nodes then it is called Full Binary Tree.

If heigh is 2 then number of nodes are 2^(2+1) – 1 = 2^3 – 1 = 8 – 1 = 7.
In the above picture, tree-1 is a full binary tree.

Array Representation of Binary Tree
Full Binary tree


💡 What is a Complete Binary Tree?

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled from the left to the right direction.

You can also say this like, a complete binary tree is a full binary tree up to height (h – 1) and the last level of the tree is filled from left to right.

In the above picture – tree-2 is a complete binary tree but not a full binary tree.


💡 Let’s Understand Binary tree with Array Representation.

Array Representation of Binary Tree


To storing a binary tree, we need to take care of two things especially.
First is we have to store all of the elements and the second is to store the relationship of nodes means who is a parent and who is a child, who is the left one, and who is the right child. So let’s see how we preserve this in an array.

To store elements in the array we read its level by level from left to right. See the first tree in the above picture, all elements are filled by level by level.

And the relationship between nodes is formed by some formulas.

If node is at index i then ->

parent node -> floor((i - 1) / 2)
left child ->  2*i + 1
right child -> 2*i + 2

Evaluate tree 1 from the above diagram –

Find parent of F.

Index of F = 5
Parent Index	= floor((5-1) / 2)
		= floor(2)
		= 2

So if see the array, we can find that C is an element on index 2. It is clear that the parent of F is C and same we can check in a tree as well.

Left Child of F = 2*i + 1
		= 2 * 5 + 1
		= 11.

There is no item in the array at index 11, it means no left child exists on node F, and same we can check in the tree as well.


💡 Let’s Understand the Complete Binary tree definition in terms of array representation.

The most important thing we have to take care of during filling the array, we have to left an empty cell in case of any child is not present in the tree.

Array Representation of Binary Tree
Empty Cells in the array where no child exists

When we represent a tree in an array then from the first element to the last element, if there is no missing element so it is called Complete Binary Tree.
In the above picture, the showing tree is not complete because there is a missing item in the array from the first to the last item.


💡 In Below Picture Find out Complete Tree –

Complete Binary tree

1 – [1, 2, 3, 4] – Complete Binary Tree

2 – [1, 2, 3, -, -, 4] – Not a Complete Binary Tree

3 – [1, 2, 3, 4, 5] – Complete Binary Tree

4 – [1, 2, 3, -, 4, -, 5] – Not a Complete Binary Tree

5 – [1, 2, -, 3] – Not a Complete Binary Tree

6 – [1, 2, 3, 4, 5, 6] – Complete Binary Tree

*****************

Array Representation of Binary Tree

Leave a Reply

Your email address will not be published.