Binary trees Representation

Binary trees can be represented in computer memory in mainly two ways:

1. Array Representation

In the array representation of a binary tree, the tree elements are stored in an array, and the parent-child relationship is maintained through the indices of the array.

Indexing Rules

• If the root node is stored at index 0, then for any node stored at index i, its left child is stored at index 2i + 1 and its right child at index 2i + 2.
• Conversely, the parent of a node at index i can be found at index floor((i-1)/2).

Characteristics

• Space Efficiency: For complete or nearly complete binary trees, array representation is space-efficient. However, for sparse trees, it can waste a lot of space due to the empty slots in the array.
• Performance: Accessing nodes, as well as their children and parents, is fast because it involves simple arithmetic operations on indices.
• Limitations: The size of the tree is fixed and needs to be known in advance, or resizing the array might be required, which is a costly operation.

Use Cases: This representation is often used in implementations of binary heaps, where the tree is mostly complete and the array-based approach is space-efficient and fast.

2. Linked List Representation

In the linked list representation, each node of the tree is represented as an object with typically three attributes: the data part, a pointer/reference to the left child, and a pointer/reference to the right child.

Node Structure

• Each node contains the element and two pointers or references, one for each child.
• The pointers are set to null (or a similar sentinel value) for leaf nodes for their non-existing children.

Characteristics

• Space Efficiency: This method is more space-efficient for sparse trees, as it allocates memory only for existing nodes.
• Dynamic Size: The tree can grow or shrink dynamically, allowing for more flexibility in operations like addition or deletion of nodes.
• Performance: Accessing children or parent nodes requires following pointers, which might be slightly slower than direct index-based access in arrays.
• Overhead: Each node requires extra memory for the pointers, in addition to the data it stores.

Use Cases: The linked list representation is the more common and general-purpose approach, especially when the tree is dynamic, or its shape cannot be predicted or is highly variable.