Memory Representation of Binary Tree

In the array representation of binary tree, we store the nodes of a binary tree in an array level by level, left to right starting from the root node till all the leaf nodes are stored.

The size of the array TREE can be determined using the property of binary tree according to which a binary tree of height h can have atmost 2^h+1-1 nodes.Therefore, the size of array tree is 2^h+1-1.

We can store the nodes of binary tree as follows:

1. The root node A will be stored at index 1 i.e. at TREE[1].

Map Nodes to Array Indices when root node at index 0:

• Its left child is at index 2*i + 1.
• Its right child is at index 2*i + 2.
• Its parent is at index (i-1) / 2.

Map Nodes to Array Indices when root node at index 1:

• Its left child is at index 2*i.
• Its right child is at index 2*i + 1.
• Its parent is at index i/2.

Binary Tree Example:

//Binary Tree program using array
//Binary Tree program using array
#include<iostream>
using namespace std;
#define ARRAY_SIZE 10

int index=-1;
int binaryTree[ARRAY_SIZE];
void initTree()
{
for(int i=0;i<ARRAY_SIZE;i++)
{
binaryTree[i]=-1;//initialize with -1 (empty nodes)
}
}//end of initArray function
void insertNode1(int key)
{
index++;
binaryTree[index]=key;
}//end of function
void printTree()
{
for (int i = 0; i < ARRAY_SIZE; i++)
{
cout << binaryTree[i]<< " ";
}

}//end of function
int main()
{
initTree();
insertNode1(10);
insertNode1(20);
insertNode1(30);
insertNode1(40);
insertNode1(50);
insertNode1(60);
insertNode1(70);
printTree();
return 0;
}//end of main

Output:

10 20 30 40 50 60 70 -1 -1 -1

Array Representation of Binary Tree with values: 10,20,30,40,50,60,70

Binary Tree with values: 10,20,30,40,50,60,70

1. The nodes are arranged in a specific order. This is also called ordered binary tree.
2. The value of all the nodes in the left sub-tree is less than the value of the root.
3. The value of all the nodes in the right sub-tree is greater than or equal to the value of the root.

BST Example:

//Binary Search Tree program using array
#include<iostream>
using namespace std;
#define ARRAY_SIZE 10

int binaryTree[ARRAY_SIZE];
void initTree(){
for(int i=0;i<ARRAY_SIZE;i++)
{
binaryTree[i]=-1;//initialize with -1 (empty nodes)
}
}//end of initArray function
void insertNode1(int key,int index=0)
{
if(binaryTree[index]==-1)
{
binaryTree[index]=key;
return;
}
// If current node is not empty, recurse to left or right child
if (key < binaryTree[index]) {
insertNode1(key, 2 * index + 1); // Go to left child
} else {
insertNode1(key, 2 * index + 2); // Go to right child
}
}//end of function
void printTree() {
for (int i = 0; i < ARRAY_SIZE; ++i) {
if (binaryTree[i] != -1) {
cout << binaryTree[i] << " ";
} else {
cout << "- ";
}
}
cout << "\n";
}//end of function
int main()
{
initTree();
insertNode1(10);
insertNode1(200);
insertNode1(30);
printTree();
return 0;
}//end of main

Output:

10 - 200 - - 30 - - - -

Array Representation of BST with values: 10,200,30

BST with values: 10,200,30