A tree is binary if each if each node of the tree can have maximum of two children. Moreover, children of a node of binary tree are ordered. One child is called the “left” child and the other us called the “right” child.
Node A has two children B and C. Similarly, nodes B and C, each have one child namely G and D respectively.
Representation of a Binary tree using an array:
In order to represent a tree in a single one-dimensional array, the nodes are numbered sequentially level by level left to right. Even empty nodes are numbered.
When the data of the tree is stored in an array then the number appearing against the node will work as indices of the node in an array.
Location number zero of the array can be used to store the size of the tree in terms of total number of nodes (existing or not existing).
- All non-existing children are shown by “\0” in the array.
- Index of the left child of a node i= 2 x i
- Index of the right child of a node i= 2x i+1
- Index of the parent of a node i= i/2
Sibling of a node i will be found at the location i + 1, if i is a left child of its parent. Similarly, if i is a right child of its parent then its sibling will be found at i-1.