Binary Tree Representation

Binary Tree Representation

There two types of binary tree representations ‒

1) Array representation (Dynamic node representation)

• In this representation, we store the tree in an array using index relationships. For a node at index i

• The root node is placed at index 0.

• Left child : Index is calculated using the formula 2*i + 1

• Right child : Index is calculated using the formula 2*i + 2

• Parent : Index is calculated using the formula floor(i‒1)/2

For example

Advantages

1. Very fast access to parent/children using fixed formula.

2. Memory is contiguous so good cache performance.

3. This representation serves as a simple implementation for complete binary trees.

4. This representation is also useful for binary heap structure.

Disadvantages

1. There is wastage of lot of memory when tree is not complete or sparse.

2. This representation is not suitable for dynamic or skewed trees.

3. The size of the tree must.

4. Insertion and deletion operations are difficult.

2) Linked representation(Sequential representation)

In binary tree each node will have left child, right child and data field.vi

The left child is nothing but the left link which points to some address of left sub‒tree whereas right child is also a right link which points to some address of right sub‒tree. And the data field gives the information about the node. Let us see the 'C' structure of the node in a binary tree.

typedef struct node

{

   int data;

   struct node *left;

   struct node *right;

}bin;

The tree with linked representation is as shown below.

Advantages

1. Dynamic size grows or shrinks as needed.

2. It is efficient representation when the tree is sparse.

3. The insertion and deletion operations are performed without shifting elements.

4. This representation can represent any type of binary tree such as complete, skewed, expression tree.

Disadvantages

1. There is extra memory overload due to pointers.

2. Accessing children nodes is slower because of pointer dereferencing.

4. For insertion and deletion of nodes from the tree using linked representation, there is a need to allocate or deallocate the memory.