**How can we represent an arbitrary***binary tree* in an *array*? In fact, there are numerous ways to do this, we’ll just look at one.

*binary tree*in an

*array*? In fact, there are numerous ways to do this, we’ll just look at one.

**Answer: –** Because an array’s length is fixed at compile time, if we use an array to implement a tree we have to set a limit on the number of nodes we will permit in the tree. Our strategy is to fix the maximum *height* of the tree (H), and make the array big enough to hold any binary tree of this height (or less). We’ll need an array of size (2**H)-1. Here is the biggest binary tree of depth 3:

If we picked H=3 as our limit, then every tree we might build will be a *sub tree* of this one – this is the key insight behind our implementation.

What we do now is assign each of nodes to a specific position in the array. This could be done any way you like, but a particular easy and useful way is:

- root of the tree (A): array position 1
- root’s left child (B): array position 2
- root’s right child (C): array position 3
- …
- left child of node in array position K: array position 2K
- right child of node in array position K: array position 2K+1

So D is in position 2*2 (4), E is in position 2*2+1 (5), F is in position 2*3 (6), G is in position 2*3+1 (7). This figure shows the array position associated with each node: –

This particular arrangement makes it easy to move from a node to its children, just double the node’s index (and add 1 to go right). It also makes it easy to go from a node to its parent: the parent of node I has index (I div 2).

Using this strategy, a tree with N nodes does not necessarily occupy the first N positions in the array. For example, the tree:

Somehow we need to keep track of which array elements contain valid information. Two possibilities:

- as usual, each node stores information saying which of its children exist
- each array position stores information saying if it is a valid node.

However, if we restrict ourselves to *complete* trees, these problems go away. Because of the way we assigned nodes to positions, if there are N nodes in a complete tree, they will correspond to the first N positions of the array. So:

- only need to keep track of N in order to know which array positions contain valid information.
- if we add a new value, it must go in position N+1; if we delete a value, we must re-organize the tree so that the `gap’ created by deleting is filled.
- can traverse the tree by going through the array from first to Nth position.

*for(i=0;i<N;i++) { process node in position i; }*

This gets us level-by-level traversal!

To see this `amazing’ fact, look again at the earlier picture.

We have insisted that heaps be complete trees precisely so that they will have this very nice implementation in arrays. It is a useful exercise to work through the insert and delete operations for heaps in this array representation: the textbook gives code implementing INSERT and DELETE for this representation (*(pp.279-80)*).