Representation of Binary Trees in Memory

Binary trees in memory can be represented by

Representation through Arrays

Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :

    1. The values of binary tree is stored in an array called as tree.
    2. The root of the tree is stored at first location i.e. at  tree[0](0 index).
    3. The left child of tree is stored at  2i +1 and right child is stored at  2i+2 location.
    4. The maximum size of the array tree is given as  2d+1-1, where d is the depth of the tree.
    5. An empty tree or sub-tree is specified using NULL. If tree[0] = NULL, then it means that tree is empty.
Screen Shot 2014-05-05 at 4.20.55 PM

Fig 1 : Array Representation of Binary Tree

Screen Shot 2014-05-05 at 4.34.11 PM

Representation through Linked List

In linked list representation,every node of the tree has three parts : the data/root element,the pointer to the left node and the pointer to the right node(Fig 2).In C,tree is built using structures by the following way :

struct node
 struct node* left; 
     int data;
  struct node* right;


Fig 2 : Linked List Representation of Binary Trees

Fig 2 : Linked List Representation of Binary Tree



Short URL:
Author: Cusp2207 on May 6, 2014
Category: Computer Science, Data Structures

Leave a Reply

Last articles