Binary Tree- Representation in Memory

A binary tree is a non-linear data structure to maintain binary relationships among elements.  Binary trees are special trees where a node can have maximum two child nodes. These are on the left and right side of a given nodes so called left child and right child nodes. These trees are best used to store decision trees which represent decisions involving yes or no, true or false or 0 or 1. They are most frequently used in gaming applications where only two moves are possible to be taken by a player. It stores various states that may be achieved after a move is taken by a player.

Memory Representation-Array

A small and almost complete binary tree can be easily stored in a linear array.  Small tree is preferably stored in linear array because searching process in a linear array is expensive. Complete means that if most of the nodes have two child nodes.

To store binary tree in a linear array, you need to consider the positional indexes of the nodes. This indexing must be considered starting with 1 from the root node going from left to right as you go down from one level to other.

Binary Tree

Assigning of indexes is done in this way-

Index of parent= INT[index of child node/2]
Index of Left Child = 2 * Index of parent
Index of Right Child = 2 * Index of parent+1

These rules are used to store the tree of the above example in an array

Array representation

If a binary tree contains less number of elements by is deep In structure, the memory underutilization is a major issue.

Binary Tree in a Linked Representation

In linked and dynamic representation, the linked list data structure is used. Each node constitutes of a data part and two link parts. The two link parts store address of left and right child nodes. Data part is used to store the information about the binary tree element. This is a better representation as nodes can be added or deleted at any location. Memory utilization is better in this binary tree representation.

Linked representation

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *