Representing Binary trees in memory

Let T be a binary tree. The two ways of representing T in memory are:

1. Link representation (Linked list)
2. Sequential representation (Array)

Linked representation of binary trees

Consider a binary tree T. unless otherwise stated or implied, T will be maintained in memory by means of a linked representation which uses three parallel arrays, INFO, LEFT and RIGHT, and a pointer variable ROOT as follows. First of all, each node N of T will correspond to a location K such that:

• INFO[K] contains the data at the node N.
• LEFT[K] contains the location of the left child of node N.
• RIGHT[K] contains the location of the right child of node N.

Furthermore, ROOT will contain the location of the root R of T. If any subtree is empty, then the corresponding pointer will contain the null value; if the tree T itself is empty, then ROOT will contain the null value.