Array Implementation of Binary Tree

There are multiple ways of implementing a binary tree. In this article, we will be discussing about the array implementation of binary trees

For example, if we want to implement a binary tree given below as an array :

Since, this binary tree contains 3 levels, to implement this tree as an array, we need
1 + 2^0 + 2^1 + 2^2 + 2^3 = 16 nodes. After that, we will store the level order traversal of the tree into the array.
So the array would look like this :
[-1, 3, 5, 6, 11, 8, 9, -1, 9, -1, -1, -1, -1, -1, -1, -1 ]
-1 in the above array means that the corresponding position is blank.
Note that the 0th position in the above array is intentionally left blank.

Parent

Using the above array implementation of binary trees, we can use the following function to find parent of any node situated at position i.

Parent(i) {
    return i/2
}

For example, the node with value 8, is situated at position 5 within the array. Therefore, according to the Parent function above, it’s parent will be located at index 5/2 = 2. The node at position 2 is 5, which is indeed the parent of node 8 as you can check from the diagram above.

Left Child

Using the array implementation of binary trees, we can use the following function to find left child of any node situated at position i

LeftChild(i) {
    return 2*i
}

For example, the node with value 5 is situated at position 2. Therefore, according to the above function, it’s left child will be located at position 2*2 = 4. The element at position 4 is 11, which is indeed the left child of 5 as can be seen from the diagram above.

Right Child

Using the array implementation of binary trees, we can use the following function to find the right child of any node situated at position i.

RightChild(i) {
    return 2*i + 1
}

For example, the node with value 5 is situated at position 2 in the array implementation of binary tree. Therefore, according to the above function, it’s right child will be located at position 2*2 + 1 = 5. The element at position 5 is 8, which is indeed the right child of 5 as can be seen from the diagram above.