Deleting a node from a binary tree involves removing a specified node while maintaining the structure of the tree. Unlike binary search trees, where specific rules help maintain ordering, general binary tree deletion may replace the node with the deepest rightmost node. Understanding deletion is essential for memory management and maintaining proper tree structure.
Understanding the Problem
The challenge in deleting a node from a binary tree is identifying the correct replacement to preserve the tree’s shape. Typically, the node to be deleted is replaced by the deepest rightmost node, ensuring that all other nodes remain connected properly. Traversal is required to locate both the target node and the deepest node.
Program: Deleting a Node from a Binary Tree
This program demonstrates how to delete a node from a binary tree by replacing it with the deepest rightmost node. The tree is traversed level by level to find the nodes.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
typedef struct Queue {
Node **arr;
int front, rear, size, capacity;
} Queue;
// Function to create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Queue functions for level order traversal
Queue* createQueue(int capacity) {
Queue *q = (Queue*) malloc(sizeof(Queue));
q->capacity = capacity;
q->front = q->size = 0;
q->rear = capacity - 1;
q->arr = (Node**)malloc(capacity * sizeof(Node*));
return q;
}
int isEmpty(Queue *q) {
return q->size == 0;
}
void enqueue(Queue *q, Node *node) {
q->rear = (q->rear + 1) % q->capacity;
q->arr[q->rear] = node;
q->size++;
}
Node* dequeue(Queue *q) {
Node *node = q->arr[q->front];
q->front = (q->front + 1) % q->capacity;
q->size--;
return node;
}
// Helper to delete the deepest node
void deleteDeepest(Node *root, Node *dNode) {
Queue *q = createQueue(100);
enqueue(q, root);
Node *temp;
while (!isEmpty(q)) {
temp = dequeue(q);
if (temp->left) {
if (temp->left == dNode) {
free(temp->left);
temp->left = NULL;
break;
} else
enqueue(q, temp->left);
}
if (temp->right) {
if (temp->right == dNode) {
free(temp->right);
temp->right = NULL;
break;
} else
enqueue(q, temp->right);
}
}
free(q->arr);
free(q);
}
// Level order traversal to delete a node
void deleteNode(Node *root, int key) {
if (!root) return;
if (!root->left && !root->right) {
if (root->data == key) {
free(root);
root = NULL;
}
return;
}
Queue *q = createQueue(100);
enqueue(q, root);
Node *temp;
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) {
int x = temp->data;
deleteDeepest(root, temp);
keyNode->data = x;
}
free(q->arr);
free(q);
}
// Inorder traversal to display tree
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
Node *root = createNode(10);
root->left = createNode(11);
root->left->left = createNode(7);
root->right = createNode(9);
root->right->left = createNode(15);
root->right->right = createNode(8);
printf("Inorder traversal before deletion: ");
inorder(root);
printf("\n");
int key = 11;
deleteNode(root, key);
printf("Inorder traversal after deleting %d: ", key);
inorder(root);
printf("\n");
return 0;
}In this program, a Node structure represents tree nodes. The deleteNode function performs a level-order traversal using a queue to locate the target node and the deepest node. The deepest node’s value replaces the target node, and the deepest node itself is deleted. This preserves the shape of the binary tree.
FAQs
Q1: Can we delete a node from a binary tree without using a queue?
Yes, but level-order traversal using a queue simplifies locating the deepest node.
Q2: What happens if the node to be deleted is the root?
The root is replaced by the deepest rightmost node, preserving tree structure.
Q3: What is the time complexity of this deletion method?
O(n), as each node may need to be visited once for locating and deletion.
Q4: Can this method be used for binary search trees?
For BSTs, specific rules exist to maintain ordering; this method applies to general binary trees.
Conclusion
Deleting a node from a binary tree requires careful handling to preserve tree structure. Using the deepest rightmost node as a replacement ensures no other nodes are disconnected. Mastering this operation is important for memory management and building reliable tree-based applications.
References & Additional Resources
A curated collection of books and online resources providing both theoretical foundations and practical examples for understanding binary trees, dynamic memory allocation, and related data structures in C.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees, dynamic memory allocation, and other fundamental data structures.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, essential for data structure implementation.
- GeeksforGeeks: Binary Tree in C – Explanation of binary tree concepts, structure, and implementation in C.
- Programiz: Data Structures – Binary Tree – Beginner-friendly guide with examples for traversal, insertion, and deletion.
- Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of
malloc(),calloc(),realloc(), andfree()functions for memory management.
