Array Representation of Binary Tree

Last Updated on March 2, 2023 by Prepbytes

In this article, we will discuss the array representation of binary trees but before diving directly into our topic we will know about binary trees in detail the critical terminologies used while working with binary trees followed by types of binary tree, we will have a good dry run of the example of array representation of binary tree followed by codes and output. At last, we will also discuss the application of binary trees followed by the demerits of using array representation of binary tree.

Binary Trees

Binary trees are a type of data structure used for searching, storing, and retrieving elements in an efficient manner. It consists of nodes connected in a tree-like fashion where each node has a maximum of two children nodes. The node at the top of the tree is called the root node, while the nodes that have no children are called leaf nodes.

Each node in a binary tree contains a value and references to its left and right children nodes. The left child is typically used to store values less than the node’s value, and the right child is used for values greater than the node’s value. This structure allows for searching for a specific value in the tree to take place in logarithmic time, making binary trees an efficient data structure for large data sets.

Binary trees can be implemented using a variety of methods, including binary search trees and balanced trees, each with its own advantages and disadvantages. Binary search trees are simple to implement and have the benefit of searching for elements in logarithmic time, but they can become unbalanced over time, leading to longer search times. Balanced trees, such as AVL trees or red-black trees, use rotations to keep the tree balanced, which results in more complex code but guarantees faster search times.

Terminologies used in Binary Tree

There are various terms or terminologies you might encounter while doing anything with binary trees whether traversal in binary trees or array representation of binary tree. Some of the important key terms are discussed below:

1. Root: The root node of the binary tree is the first node in the graph. Since the root node is the starting point of the tree and lacks any parent elements, there cannot be any tree without one. In a tree, there can only be one root node.
2. Edge: The margins of the tree, sometimes referred to as the branch of a tree, are the connecting link between the two nodes. A binary tree will have n nodes and n-1 edges if there are n nodes.
3. Parent: A parent node is a node that connects to another node at the level beneath it. A node that is a predecessor of another node is referred to as a parent node in a more formal sense.
4. Child: The term "child node" refers to any node that is connected to a node that is one level above it. Informally, any note that is a descendent of a node is referred to as a child node. Except for the root node, every node that is absent from the tree can be thought of as a child node.
5. Siblings: The child nodes that have the same parent are known as siblings.
6. Leaf: It is the node that does not have any child or the node with zero child nodes is known as a leaf node.
7. Internal Node: The node that has atleast one child node corresponding to it is known as an internal node or one can say that all the nodes of a tree except the leaf nodes are internal nodes.
8. Ancestors: A node’s ancestors are the nodes that are on its journey from the root to the current node, including the root node, but not the current node.
9. Descendants: A node’s descendants are the nodes that are below it in level and related to it either directly or indirectly through other nodes. The current node’s descendants include all of its children, their offspring, and so forth.
10. Path: A path between any two nodes of a tree is made up of the edges connecting the nodes as well as the linked nodes in that order. And the distance between two nodes, measured in nodes, is the route length.
11. Level: It denotes how far is the node from the top of the tree or the root node as how many steps we need to go down to reach the node. The level increases as we move downwards.
12. Depth: It denotes the number of nodes in the path from the root node to a targeted node or a particular node.

Types of Binary Tree

There are many types of binary trees available we’ll look into some examples of them before moving to the array representation of binary tree.

1. Full Binary Tree: A full binary tree is a binary tree where every node has either 0 or 2 children. No node can have only 1 child. This type of tree is also known as a strict binary tree. In a full binary tree, the number of leaf nodes is equal to the number of internal nodes plus 1. This type of tree is often used to represent hierarchical relationships, as each node can have a parent and two children.

2. Perfect Binary Tree: A perfect binary tree is a full binary tree where all leaf nodes are at the same depth and all internal nodes have two children. The height of a perfect binary tree is log2n, where n is the number of nodes in the tree. This type of tree is often used in computer algorithms, as it allows for efficient representation and processing of data.

3. Complete Binary Tree: A complete binary tree is a binary tree where every level is completely filled, except for possibly the last level, which is filled from left to right. This type of tree is often used in algorithms that require data to be stored in a heap structure, such as a priority queue or heap sort. The advantage of using a complete binary tree over other types of trees is that the tree can be efficiently stored in an array.

4. Degenerate Binary Tree: A degenerate binary tree is a tree in which every internal node has only one child. This results in a tree that is similar to a linked list. Degenerate trees are not commonly used in computer algorithms, as they do not provide efficient access to data. In many cases, a degenerate tree can be replaced with a more efficient data structure, such as an array or linked list.

5. Balanced Binary Tree: A balanced binary tree is a binary tree where the height difference between the left and right subtrees of any node is no greater than some constant value. This helps ensure fast search times and prevent the tree from becoming too unbalanced. Examples of balanced binary trees include red-black trees and AVL trees. These trees are commonly used in computer algorithms and data structures that require fast access to data, such as search trees and heaps. The advantage of using a balanced binary tree is that search times are guaranteed to be logarithmic, ensuring efficient access to data.

Explanation of Array Representation of Binary Tree

The array representation of binary tree can be done using a technique called level order traversal. In level-order traversal, the elements of the binary tree are stored in the array in the order in which they are visited in a breadth-first search.
The array representation of binary tree allows for efficient access to the elements of the tree. For example, if a binary tree has n nodes, the array representation of the tree can be stored in an array of size n, allowing for constant-time access to each node in the tree.
In this representation, the root node of the binary tree is stored at the first position of the array, and its left and right children are stored at the second and third positions, respectively. The remaining nodes are stored in the same way, with the children of each node stored in consecutive positions in the array.
For example, consider the following binary tree:

      1
     / \
    2   3
   / \  
  4   5

The level order representation of this tree in an array would be [1, 2, 3, 4, 5].
Using this representation, it is possible to access the children of a node at position i by using the following formulas:

The left child of node i can be found at position 2i + 1
The right child of node i can be found at position 2i + 2
It is also possible to determine the parent of a node at position i using the formula:
The parent of node i can be found at position (i – 1) / 2
The array representation of binary tree can be useful in algorithms that require fast access to the elements of a tree, such as searching or sorting algorithms. However, it is important to note that not all binary trees can be efficiently represented in an array, as the number of elements in the array must be known in advance. Additionally, some algorithms may require a different representation of a binary tree, such as a linked list representation.

Dry Run of Array Representation of Binary Tree with Example

For the array representation of binary tree, we will form an array of size 2*n+1 size where n is the number of nodes the binary tree. Now we will move step by step for the array representation of binary tree.

1. First, suppose we have a binary tree with seven nodes

2. Now, for the array representation of binary tree, we have to give numbering to the corresponding nodes. The standard form of numbering the nodes is to start from the root node and move from left to right at every level .After numbering the tree and nodes will look like this:

3. Now as we have numbered from zero you can simply place the corresponding number in the matching index of an array then the array will look like this:

4. That is the array representation of binary tree but this is the easy case as every node has two child so what about other cases? We will discuss other cases below.

5. In these cases, we will discuss the scenarios for the array representation of binary tree where there the lead node is not always on the last level.

6. So consider the binary tree given below:

7. While giving a number you are stuck with the cases where you encounter a leaf node so just make the child node of the leaf nodes as NULL then the tree will look like this:

8. Now just number the nodes as done above for the array representation of binary tree after that the tree will look like this:

9. Now we have the number on each node we can easily use the tree for array representation of binary tree and the array will look like this:

Example of Array Representation of Binary Tree

In this section, we will look at the code of the implementation of the example of binary tree with output and proper explanation of the output.

Code Implementation:

#include<bits/stdc++.h>
using namespace std;
char tree[10];
int root(char key) {
if (tree[0] != '\0')
    cout << "Tree already had root";
else
    tree[0] = key;
return 0;
}

int left_set(char key, int parent) {
if (tree[parent] == '\0')
    cout << "\nCan't set child at "
    << (parent * 2) + 1
    << " , no parent found";
else
    tree[(parent * 2) + 1] = key;
return 0;
}

int right_set(char key, int parent) {
if (tree[parent] == '\0')
    cout << "\nCan't set child at "
    << (parent * 2) + 2
    << " , no parent found";
else
    tree[(parent * 2) + 2] = key;
return 0;
}

int print_tree() {
cout << "\n";
for (int i = 0; i < 10; i++) {
    if (tree[i] != '\0')
    cout << tree[i];
    else
    cout << "-";
}
return 0;
}

// Driver Code
int main() {
root('A');
left_set('B',0);
right_set('C', 0);
left_set('D', 1);
right_set('E', 1);
right_set('F', 2);
left_set('G', 3);
right_set('H', 3);

print_tree();
return 0;
}

Output

ABCDE-FGH-

Explanation of the above code
In the above code, we have shown the array representation of binary tree where we have set the left and right child correspondingly by passing to the function and in case of no node present we have represented by a ‘-’.

Applications of Binary Tree

Here we will discuss some of the applications of Binary Trees in detail:

1. Data representation and storage: Binary trees are commonly used to store data in an organized, hierarchical manner, where each node has at most two child nodes.
2. Searching: Binary search trees allow for efficient searching of data as it is structured in a manner that enables a binary search approach.
3. Sorting algorithms: Binary trees can be used to implement sorting algorithms, such as Heap sort.
4. Expression trees: Binary trees can be used to store expression trees, which are used to evaluate expressions in the mathematically correct order.
5. Path finding: Binary trees can be used to find the shortest path in a graph or network, as in Dijkstra’s algorithm.
6. Decision-making algorithms: Binary trees can be used to implement decision-making algorithms, such as ID3 (for decision tree learning).

Advantages of Array Representation of Binary Tree

Advantages of Array Representation of Binary Trees are mentioned below:

1. Easy to implement: Array representation of binary trees is simple to implement and understand.
2. Memory efficient: Array representation takes less memory compared to linked representation, as there are no pointers to be stored.
3. Easy to access children: Children of a node can be easily accessed in an array representation as the indices for left and right children are easily computable.
4. Traversals are efficient: Array representation allows for efficient traversals, such as pre-order, in-order, and post-order.
5. Space utilization: Array representation can utilize space efficiently, as all the memory is contiguous and not spread out.

Disadvantages of Array Representation of Binary Tree:

Some of the disadvantages of Array Representation of Binary Trees are given below:

1. Difficult to insert and delete nodes: Inserting and deleting nodes in an array representation is complex, as the structure needs to be re-arranged.
2. Limited to complete trees: Array representation is limited to complete trees and cannot handle cases where there are missing nodes in a tree.
3. Limited flexibility: Array representation has limited flexibility and cannot handle trees with an unpredictable number of nodes.
4. Fixed size: The size of an array must be pre-determined, so if the tree grows beyond the size of the array, it cannot be resized dynamically.
5. No explicit pointers: Array representation does not have explicit pointers to parent or child nodes, making it harder to navigate the tree in certain cases.

Conclusion
In this blog, we have learned about binary trees, and key terminologies used in binary trees, types of binary tree, followed by an array representation of binary tree, first with a dry run of an example with step by step explanation of the same after that the code-implementation of the array representation of the binary tree, followed by the application of binary tree and ended with the advantages and disadvantages of array representation of binary tree.