Binary trees Representation
Binary trees can be represented in computer memory in mainly two ways:
- Array Representation
- Linked List Representation.
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.
Next Topic :Binary tree traversals