.png)
[Follow here] for daily coding insights
DSA Series Chapter 19 : DELETION IN BINARY TREE(C Version)
1. Objective
To delete a given key value from a Binary Tree by:
Finding the deepest rightmost node
Replacing the target node’s data with it
Deleting the deepest node
This method maintains the complete binary tree structure.
2. Important Concept
Unlike BST deletion, a general Binary Tree:
Has no ordering
Cannot simply rearrange children
Uses Level Order Traversal (BFS)
Hence, deletion is performed using the deepest node technique.
3. Binary Tree Diagram
Before Deletion (Delete 2)
1
/ \
2 3
/ \ /
4 5 6
Step 1: Deepest Node = 6
Step 2: Replace 2 with 6
After Deletion
1
/ \
6 3
/ \
4 5
4. Deletion Algorithm (High-Level)
If tree is empty → return
Use queue for level order traversal
Find:
Node to delete (key node)
Deepest rightmost node
Copy deepest node data into key node
Delete deepest node physically
5. Data Structures Used
5.1 Node Structure
struct Node {
int data;
struct Node *left;
struct Node *right;
};
5.2 Queue Structure (For BFS)
struct Queue {
int front, rear;
struct Node* arr[100];
};
6. Queue Operations
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. Function to Delete Deepest Node
void deleteDeepest(struct Node* root, struct Node* dNode) {
struct Queue q;
initQueue(&q);
enqueue(&q, root);
while (!isEmpty(&q)) {
struct Node* temp = dequeue(&q);
if (temp->left) {
if (temp->left == dNode) {
free(temp->left);
temp->left = NULL;
return;
}
enqueue(&q, temp->left);
}
if (temp->right) {
if (temp->right == dNode) {
free(temp->right);
temp->right = NULL;
return;
}
enqueue(&q, temp->right);
}
}
}
9. Deletion Function (CORE LOGIC)
void deleteNode(struct Node* root, int key) {
if (root == NULL)
return;
struct Queue q;
initQueue(&q);
enqueue(&q, root);
struct Node* temp;
struct Node* keyNode = NULL;
while (!isEmpty(&q)) {
temp = dequeue(&q);
if (temp->data == key)
keyNode = temp;
if (temp->left)
enqueue(&q, temp->left);
if (temp->right)
enqueue(&q, temp->right);
}
if (keyNode != NULL) {
int x = temp->data;
deleteDeepest(root, temp);
keyNode->data = x;
}
}
10. 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 deleteDeepest(struct Node* root, struct Node* dNode) {
struct Queue q;
initQueue(&q);
enqueue(&q, root);
while (!isEmpty(&q)) {
struct Node* temp = dequeue(&q);
if (temp->left) {
if (temp->left == dNode) {
free(temp->left);
temp->left = NULL;
return;
}
enqueue(&q, temp->left);
}
if (temp->right) {
if (temp->right == dNode) {
free(temp->right);
temp->right = NULL;
return;
}
enqueue(&q, temp->right);
}
}
}
void deleteNode(struct Node* root, int key) {
if (root == NULL)
return;
struct Queue q;
initQueue(&q);
enqueue(&q, root);
struct Node* temp;
struct Node* keyNode = NULL;
while (!isEmpty(&q)) {
temp = dequeue(&q);
if (temp->data == key)
keyNode = temp;
if (temp->left)
enqueue(&q, temp->left);
if (temp->right)
enqueue(&q, temp->right);
}
if (keyNode != NULL) {
int x = temp->data;
deleteDeepest(root, temp);
keyNode->data = x;
}
}
void inorder(struct Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
printf("Before Deletion (Inorder): ");
inorder(root);
deleteNode(root, 2);
printf("\nAfter Deletion (Inorder): ");
inorder(root);
return 0;
}
11. Output
Before Deletion (Inorder): 4 2 5 1 6 3
After Deletion (Inorder): 4 6 5 1 3
12. Time and Space Complexity
| Operation | Complexity |
|---|---|
| Deletion | O(n) |
| Space | O(n) |
13. Key Differences: BT vs BST Deletion
| Feature | Binary Tree | BST |
|---|---|---|
| Ordering | No | Yes |
| Traversal | BFS | DFS |
| Node Replacement | Deepest Node | Inorder Successor |
14. Common Student Mistakes
Forgetting to delete deepest node
Using recursion incorrectly
Assuming BST logic applies
Not using queue
15. Learning Outcome
After this post, students can:
Delete nodes correctly in Binary Tree
Apply BFS for structural integrity
Understand memory handling in C
Distinguish BT and BST deletion
ALSO CHECK
ALSO CHECK
Comments
Post a Comment