Dynamic Representation of Binary Tree

Dynamic Representation of a Binary Tree

In a dynamic representation of a binary tree, each node is created dynamically using pointers. A node typically consists of:

A data field that stores the value of the node.
Two pointers (or references) to its left child and right child.

Unlike array-based representations, where the structure and size of the tree are predefined, a dynamic representation allows the tree to grow or shrink as needed. The memory for each node is allocated only when it is created, making it more flexible and memory-efficient, especially for trees with an unpredictable or changing number of nodes.

Key Features :

Memory Allocation: Nodes are created on the heap using malloc() or new (in C++), allowing for dynamic memory allocation.
Pointer-Based Connections: Each node points to its children, forming a flexible structure where the size and shape of the tree can be changed during runtime.
Efficient Storage: Memory is used only for the nodes that are added, unlike the array-based approach that may waste space for unused indices.

In a dynamic representation of a binary tree, a node is created using dynamic memory allocation. The node is typically represented by a struct (in C/C++), and it contains the data field as well as two pointers (left and right) to its child nodes.

Steps to Create a Node:

Define the Structure (Node) A struct is used to define the layout of the node. It typically contains:

A data field to store the value of the node.
Two pointers, one for the left child and one for the right child.

Example :

struct Node {

int data; // Stores the data of the node struct

Node* left; // Pointer to left child struct

Node* right; // Pointer to right child

};

2. Dynamically Allocate Memory for the Node To create a node, we use dynamic memory allocation with malloc() in C (or new in C++) to allocate memory on the heap.

Example:

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

3. Initialize the Node’s Data and Pointers After allocating memory for the node, we can set the node’s data and initialize the pointers (usually to NULL for the left and right children).

Example:

newNode->data = value; // Assign data to the node

newNode->left = NULL; // Left child is initially NULL

newNode->right = NULL; // Right child is initially NULL

Complete Program

#include <stdlib.h>

// Node structure for the binary tree
struct Node {
    int data;               // Data stored in the node
    struct Node* left;      // Pointer to the left child
    struct Node* right;     // Pointer to the right child
};

// Function to create a new node
struct Node* createNode(int value) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return NULL; // Return NULL if memory allocation fails
    }

    // Initialize node data and set left/right pointers to NULL
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode; // Return the newly created node
}

int main() {
    // Create nodes dynamically
    struct Node* root = createNode(10);      // Create root node with value 10
    struct Node* leftChild = createNode(5);  // Create left child with value 5
    struct Node* rightChild = createNode(15); // Create right child with value 15

    // Check if memory allocation was successful
    if (root == NULL || leftChild == NULL || rightChild == NULL) {
        printf("Error creating nodes. Exiting program.\n");
        return 1; // Exit the program if any node creation fails
    }

    // Connect the nodes to form the binary tree
    root->left = leftChild;   // Set left child of root
    root->right = rightChild; // Set right child of root

    // Print the values of the nodes
    printf("Root node: %d\n", root->data);
    printf("Left child: %d\n", root->left->data);
    printf("Right child: %d\n", root->right->data);

    // Free the allocated memory (optional for small programs, but good practice)
    free(leftChild);
    free(rightChild);
    free(root);

    return 0; // End of program
}

Dynamic Representation of a Binary Tree

Steps to Create a Node:

Complete Program

Quick Links

Help and Support