Binary Tree Array Implementation

A binary tree can be represented using an array, where each node's position is calculated using index arithmetic instead of explicit pointers. This representation is common for complete binary trees such as heaps.

Index Formulas

For a node stored at index i (0-based):

• Left child: 2*i + 1
• Right child: 2*i + 2
• Parent: (i - 1) // 2

class ArrayBinaryTree:
    def __init__(self, size):
        self.tree = [None] * size

    def insert(self, index, value):
        if index >= len(self.tree):
            self.tree.extend([None] * (index - len(self.tree) + 1))
        self.tree[index] = value

    def left_child(self, index):
        left = 2 * index + 1
        return self.tree[left] if left < len(self.tree) else None

    def right_child(self, index):
        right = 2 * index + 2
        return self.tree[right] if right < len(self.tree) else None

    def parent(self, index):
        if index == 0:
            return None
        return self.tree[(index - 1) // 2]

Advantages

• No pointer/reference overhead — child and parent lookups are simple arithmetic.
• Cache-friendly due to contiguous memory storage.
• Ideal for complete binary trees, such as binary heaps.

Disadvantages

• Wastes memory for sparse or unbalanced trees, since empty slots must still be allocated.
• Resizing the array can be costly if the tree grows dynamically.

Applications

• Binary Heap implementation (min-heap / max-heap).
• Segment trees and Fenwick trees.
• Efficient priority queues.