Lecture 271:- Representation of Binary Tree

There are several ways to represent a binary tree in computer memory. Each representation has its advantages and is suitable for different scenarios. The main representations of a binary tree are as follows:

1. Linked Representation (Node-based representation): In this representation, each node of the binary tree is represented as an object or a struct that contains three fields:

   • Data: The value or data stored in the node.
   • Left Child: A pointer or reference to the left child node.
   • Right Child: A pointer or reference to the right child node.

   Using this linked representation, we can easily create a binary tree by connecting nodes together through pointers. The root of the tree is a pointer to the topmost node. If a node has no left or right child, the corresponding pointer is set to NULL (or nullptr in C++).

2. Array-based Representation (Sequential representation): In this representation, a binary tree is stored in an array, where each index of the array represents a node, and the values stored in the array represent the data in the nodes. The relationship between parent and child nodes is determined by the indices of the array elements.

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

   • Its left child is at index 2*i + 1.
   • Its right child is at index 2*i + 2.

   This representation is space-efficient as it avoids the use of pointers. However, it may waste some space when the binary tree is not a complete binary tree.

3. Recursive Node-based Representation (using struct/class without explicit pointers): In some programming languages (e.g., Python), binary trees can be represented using a recursive approach where each node contains references to its left and right subtrees directly, without the need for explicit pointers. This approach takes advantage of the language's native recursive data structures and can make the code more concise.

Each representation has its own advantages and disadvantages, and the choice of representation depends on the specific use case and the requirements of the problem being solved. The linked representation is the most common and flexible representation used for binary trees in most programming languages.