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 :

  1. Memory Allocation: Nodes are created on the heap using malloc() or new (in C++), allowing for dynamic memory allocation.
  2. 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.
  3. 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:

  1. 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 <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

};

// 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;

    }

    // Initialize node data and set left/right pointers to NULL

    newNode->data = value;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

int main() {

    // Create nodes dynamically

    struct Node* root = createNode(10);  // Create root node

    struct Node* leftChild = createNode(5);  // Create left child

    struct Node* rightChild = createNode(15);  // Create right child

    // Connect the nodes

    root->left = leftChild;

    root->right = rightChild;

    // Print the root node’s value

    printf(“Root node: %d\n”, root->data);

    printf(“Left child: %d\n”, root->left->data);

    printf(“Right child: %d\n”, root->right->data);

    return 0;

}