.png)
DSA Series Chapter 18 – INSERTION IN BINARY TREE (LEVEL ORDER, C Version)
1. Objective
To implement insertion in a Binary Tree using Level Order Traversal in C, ensuring the tree remains complete.
2. Why Level Order Insertion?
Unlike a Binary Search Tree, a general Binary Tree:
Has no ordering rule
Must preserve completeness
Inserts nodes from left to right, level by level
Hence, Level Order Traversal (BFS) is mandatory.
3. Conceptual Diagram
Before Insertion (Insert 6)
1
/ \
2 3
/ \
4 5
After Insertion
1
/ \
2 3
/ \ /
4 5 6
Insertion happens at the first vacant position.
4. Core Idea (Algorithm Logic)
If tree is empty → new node becomes root
Use a queue
Traverse nodes level by level
Insert at:
First available left child
Else first available right child
5. Data Structures Used
Node Structure
struct Node {
int data;
struct Node *left;
struct Node *right;
};
Queue Structure (Array-based)
struct Queue {
int front, rear;
struct Node* arr[100];
};
6. Queue Operations (Required for BFS)
void initQueue(struct Queue* q) {
q->front = q->rear = 0;
}
int isEmpty(struct Queue* q) {
return q->front == q->rear;
}
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
7. Node Creation Function
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;
}
8. Level Order Insertion Function (CORE LOGIC)
void insertLevelOrder(struct Node** root, int data) {
struct Node* newNode = createNode(data);
if (*root == NULL) {
*root = newNode;
return;
}
struct Queue q;
initQueue(&q);
enqueue(&q, *root);
while (!isEmpty(&q)) {
struct Node* temp = dequeue(&q);
if (temp->left == NULL) {
temp->left = newNode;
return;
} else {
enqueue(&q, temp->left);
}
if (temp->right == NULL) {
temp->right = newNode;
return;
} else {
enqueue(&q, temp->right);
}
}
}
9. Complete C Program
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Queue {
int front, rear;
struct Node* arr[100];
};
void initQueue(struct Queue* q) {
q->front = q->rear = 0;
}
int isEmpty(struct Queue* q) {
return q->front == q->rear;
}
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
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;
}
void insertLevelOrder(struct Node** root, int data) {
struct Node* newNode = createNode(data);
if (*root == NULL) {
*root = newNode;
return;
}
struct Queue q;
initQueue(&q);
enqueue(&q, *root);
while (!isEmpty(&q)) {
struct Node* temp = dequeue(&q);
if (temp->left == NULL) {
temp->left = newNode;
return;
} else {
enqueue(&q, temp->left);
}
if (temp->right == NULL) {
temp->right = newNode;
return;
} else {
enqueue(&q, temp->right);
}
}
}
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = NULL;
insertLevelOrder(&root, 1);
insertLevelOrder(&root, 2);
insertLevelOrder(&root, 3);
insertLevelOrder(&root, 4);
insertLevelOrder(&root, 5);
insertLevelOrder(&root, 6);
printf("Inorder Traversal: ");
inorder(root);
return 0;
}
10. Output
Inorder Traversal: 4 2 5 1 6 3
11. Time and Space Complexity
Time Complexity
O(n) — traversal until vacant node
Space Complexity
O(n) — queue storage
12. Key Exam Points
Binary Tree insertion ≠ BST insertion
Uses Breadth First Search
Queue is mandatory
Maintains complete tree property
13. Common Mistakes by Students
Using recursion (incorrect here)
Forgetting double pointer for root
Confusing with BST logic
Not checking left before right
14. Learning Outcome
After this post, students can:
Insert nodes correctly in a Binary Tree
Apply BFS practically
Implement queue-based tree logic
Differentiate BT and BST insertions
Below is a beginner-friendly, line-by-line explanation of POINTS 5, 6, 7, 8, and 9 from Post 4.2 – Insertion in Binary Tree (Level Order) – C Version.
POINT 5 – DATA STRUCTURES USED
5.1 struct Node
struct Node {
int data;
struct Node *left;
struct Node *right;
};
Line-by-Line Explanation
struct Node {
Defines a structure named Node
This structure represents one node of a binary tree
int data;
Stores the value of the node
Example: 1, 2, 3, etc.
struct Node *left;
Pointer to the left child
If no left child exists →
NULL
struct Node *right;
Pointer to the right child
If no right child exists →
NULL
};
Ends the structure definition
Key idea:
Each node knows:
Its own data
Where its left child is
Where its right child is
5.2 struct Queue
struct Queue {
int front, rear;
struct Node* arr[100];
};
Line-by-Line Explanation
struct Queue {
Defines a queue structure
Queue is required for Level Order Traversal (BFS)
int front, rear;
front→ index of element to be removedrear→ index where new element is inserted
struct Node* arr[100];
Array of Node pointers
Stores addresses of tree nodes
Maximum queue size = 100
};
Ends queue structure
Why queue?
Level order traversal cannot work without a queue.
POINT 6 – QUEUE OPERATIONS
6.1 Initialize Queue
void initQueue(struct Queue* q) {
q->front = q->rear = 0;
}
Explanation
void initQueue(struct Queue* q)
Function to initialize queue
qis passed by address
q->front = q->rear = 0;
Queue starts empty
Both pointers at position 0
6.2 Check if Queue is Empty
int isEmpty(struct Queue* q) {
return q->front == q->rear;
}
Explanation
return q->front == q->rear;
If front equals rear → no elements in queue
Returns
1(true) or0(false)
6.3 Enqueue Operation
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
Explanation
q->arr[q->rear++] = node;
Store node address at
rearIncrement
rearafter insertion
FIFO rule maintained.
6.4 Dequeue Operation
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
Explanation
return q->arr[q->front++];
Returns element at
frontMoves
frontforward
POINT 7 – NODE CREATION FUNCTION
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;
}
Line-by-Line Explanation
struct Node* createNode(int data)
Function returns address of a new node
malloc(sizeof(struct Node))
Allocates memory for one node dynamically
newNode->data = data;
Stores given value in node
newNode->left = NULL;
newNode->right = NULL;
New node initially has no children
return newNode;
Returns address of created node
POINT 8 – LEVEL ORDER INSERTION FUNCTION (CORE LOGIC)
void insertLevelOrder(struct Node** root, int data)
Why struct Node** root?
Root may change (first insertion)
Hence double pointer is mandatory
Step 1: Create New Node
struct Node* newNode = createNode(data);
Creates node to be inserted
Step 2: If Tree is Empty
if (*root == NULL) {
*root = newNode;
return;
}
If no root exists:
New node becomes root
Function ends
Step 3: Initialize Queue
struct Queue q;
initQueue(&q);
enqueue(&q, *root);
Queue created
Root inserted first (BFS always starts from root)
Step 4: Level Order Traversal Loop
while (!isEmpty(&q)) {
Loop until queue is empty
Step 5: Remove Front Node
struct Node* temp = dequeue(&q);
tempis current node under inspection
Step 6: Check Left Child
if (temp->left == NULL) {
temp->left = newNode;
return;
}
If left child is empty:
Insert here
Stop function
Else:
enqueue(&q, temp->left);
Add left child to queue
Step 7: Check Right Child
if (temp->right == NULL) {
temp->right = newNode;
return;
}
If right child empty:
Insert node here
Stop
Else:
enqueue(&q, temp->right);
First vacant position is always filled
POINT 9 – COMPLETE PROGRAM (HOW IT WORKS TOGETHER)
main() Function
struct Node* root = NULL;
Tree initially empty
insertLevelOrder(&root, 1);
insertLevelOrder(&root, 2);
insertLevelOrder(&root, 3);
Nodes inserted level by level
inorder(root);
Used only to verify tree structure
FINAL BEGINNER SUMMARY
Binary Tree insertion uses BFS
Queue is compulsory
Left child is checked before right
Ensures complete binary tree
This is NOT BST insertion
ALSO CHECK
ALSO CHECK
Comments
Post a Comment