Binary Tree Array Representation video (18 minutes) (Spring 2021)
It is possible to apply some rules/conventions and store a representation of a Binary Tree in an array or vector container.
Binary Search Trees using dynamically allocated memory (nodes) and pointers to left/right child nodes have some disadvantages. Allocated memory is not guaranteed to be stored contiguously, which means that jumps in memory can happen. The overheard of pointer storage can also lead to lots of storage space being used. Pointers may be 8 bytes in size on a 64-bit machine. If you are storing a small data type, 2 pointers per node could be a lot of overhead memory required.
You also can't travel from a node to its parent in many of the BST's that we have seen. This would require yet another pointer.
In a Priority Queue or Min Heap (more about these later), it is frequently necessary to visit the parent of a tree node.
To store a representation of a tree in an array, there is the requirement that the tree is Full. This means that all layers of the tree are full (have the maximum number of nodes possible, 1, 2, 4, 8, 16, etc...), except the bottom layer of the tree. The bottom layer of the tree must be filled/populated from left to right.
This tree is full. all layers (except the bottom) have the max number of nodes possible, and the bottom layer is being filled in from left to right.
A
/ \
B C
/ \ / \
D E F G
/
H
This tree is NOT full. B is missing a right child. C also has a right child but no left child. The bottom layer isn't being filled in from left to right.
A
/ \
B C
/ \
D E
Consider the following tree.
D
/ \
B F
/ \ / \
A C E G
If it was stored in an array, it could look something like this.
D B F A C E G
0 1 2 3 4 5 6
The root is at index 0. The root's children are at index 1 and 2. Node 1 has children at index 3 and 4. Node 2 has children at index 5 and 6. Etc.
Formulas for determining the index of children/parent nodes, for a given node i, are as follows:
left child = 2i + 1
right child = 2i + 2
parent = (i - 1) / 2 (using integer division!)
The size of the array (tree) must be tracked.
The size can be used to answer the question, "does some node have a left/right child?"
To answer this question, the above formulas would be used to calculate the child index. If the index < array size, then the child exists!
A node in a full tree will never have a right child without having a left child. (Since the tree levels are filled from left to right.)
Thanks to Brian Foster for writing up these notes based on the video lectures.