DSA SERIES CHAPTER 17 : CREATION OF BINARY TREE (C VERSION)

on

 


DSA SERIES CHAPTER 17 :

CREATION OF BINARY TREE (C VERSION)

Objective :

This explains how a Binary Tree is created in C using dynamic memory allocation. It establishes the foundation for all subsequent binary tree operations in Phase 4.

Focus is on:

  • Node structure

  • Memory allocation

  • Manual linking of nodes

  • Understanding tree shape through pointers

1. What Does “Creating a Binary Tree” Mean?

Exam‑ready definition:

Creating a binary tree means allocating memory for nodes dynamically and linking each node to at most two children (left and right) using pointers.

Important clarification:

  • This is not insertion logic

  • This is explicit construction of a known tree structure

2. Binary Tree Diagram Used

We will construct the following tree:

            1
          /   \
         2     3
        / \
       4   5

This exact diagram will be reflected in the C program.

3. Node Structure in C

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

Explanation

  • data → stores node value

  • left → pointer to left child

  • right → pointer to right child

4. Creating a New Node (Dynamic Allocation)

struct Node* createNode(int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Why Dynamic Memory?

  • Tree size is not fixed

  • Nodes are created at runtime

5. Full C Program – Binary Tree Creation

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* createNode(int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main()
{
    // Step 1: Create root node
    struct Node* root = createNode(1);

    // Step 2: Create left and right children of root
    root->left = createNode(2);
    root->right = createNode(3);

    // Step 3: Create children of node 2
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Binary Tree created successfully.\n");

    return 0;
}

6. Step‑by‑Step Creation Explanation

  1. Memory allocated for node 1 → becomes root

  2. Node 2 linked as left child of root

  3. Node 3 linked as right child of root

  4. Node 4 linked as left child of node 2

  5. Node 5 linked as right child of node 2

Tree structure now matches the diagram exactly.

7. Memory Representation (Conceptual)

root
 |
[1]
/   \
[2]  [3]
/ \
[4] [5]

Each node occupies separate memory blocks, connected via pointers.

8. Time and Space Complexity

Time Complexity

  • O(n) → number of nodes created

Space Complexity

  • O(n) → memory allocated for n nodes

9. Common Student Mistakes

  • Forgetting to initialize left/right pointers to NULL

  • Using local variables instead of dynamic allocation

  • Confusing tree creation with insertion logic

10. Practice Questions

  1. Modify the program to create a right‑skewed binary tree.

  2. Create a binary tree with only one child per node.

  3. Draw memory diagram for a 3‑node tree.

  4. What happens if malloc() fails?

11. Learning Outcome (Post 4.1)

After this post, a student can:



Comments

Post a Comment