Storing complete trees in arrays

Introduction

• Each node of a full binary tree can be labelled with a number in ascending order:
• This will allow us to store the nodes in an array
  • Each node will be stored at the index it is labelled with

Properties

• Root
  • The root of the tree is always at 0.
• Children
  • If a node is stored at index n, it's children with be at the indices:
    • 2n + 1
    • 2n + 2
• Parent
  • If a node is stored at index n, it's parent will be at index:

    floor((n - 1) / 2)

Code (Python)

class Tree:
    def __init__(self):
        self.data = [];

    def setValueAtIndex(self, index, value):
        self._ensureLength(index + 1)
        self.data[index] = value

    def _ensureLength(self, n):
        if(len(self.data) < n):
            self.data.extend([None] * (n - len(self.data)))

    def getValueAtIndex(self, index):
        if(len(self.data) <= index):
            return None;
        else:
            return self.data[index]

    def getChildIndices(self, index):
        return [2 * index + 1, 2 * index + 2]

    def getParentIndex(self, index):
        return (index - 1) / 2