Binary Tree using Linked List
ALGORITHM
Step 1: Start
Step 2: Define a Structure
Define a structure Node having three fields:
data → to store the value.
left → pointer to the left child.
right → pointer to the right child.
Step 3: Create a Node
Define a function createNode(value):
1. Allocate memory for a new node.
2. Assign the given value to data.
3. Initialize left and right pointers to NULL.
4. Return the new node.
Step 4: Insertion Operation
Define a function insert(root, value):
1. If root is NULL, create a new node and return it as root.
2. Else, perform level-order traversal using a queue:
Insert root into the queue.
Repeat until queue is empty:
-Remove one node (temp) from the queue.
-If temp->left is NULL, create a new node and attach it to
temp->left, then return.
-Else, enqueue temp->left.
-If temp->right is NULL, create a new node and attach it to
temp->right, then return.
-Else, enqueue temp->right.
Step 5: Deletion Operation
Define a function deleteNode(root, key):
1. If root is NULL, return NULL.
2. If tree has only one node:
If root->data == key, free the node and return NULL.
3. Perform level-order traversal to find:
Node with value = key → store in keyNode.
The deepest (last) node → store in deepest.
4. Replace keyNode->data with deepest->data.
5. Delete the deepest node from the tree by another traversal.
6. Return the updated root.
Step 6: Inorder Traversal (Left, Root, Right)
1. If the node is not NULL:
○ Recursively traverse the left subtree.
○ Visit and print the node data.
○ Recursively traverse the right subtree.
Step 7: Preorder Traversal (Root, Left, Right)
1. If the node is not NULL:
○ Visit and print the node data.
○ Recursively traverse the left subtree.
○ Recursively traverse the right subtree.
Step 8: Postorder Traversal (Left, Right, Root)
1. If the node is not NULL:
○ Recursively traverse the left subtree.
○ Recursively traverse the right subtree.
○ Visit and print the node data.
Step 9: Menu-Driven Main Function
1. Initialize root = NULL.
2. Repeat until user chooses Exit:
Display menu:
1. Insert Node
2. Delete Node
3. Inorder Traversal
4. Preorder Traversal
5. Postorder Traversal
6. Exit
Read user choice and perform corresponding operation.
Step 10: Stop
PROGRAM:Binary Tree Using Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
struct Node* temp = root;
struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = temp;
while (front < rear) {
temp = queue[front++];
if (temp->left == NULL) {
temp->left = createNode(value);
return root;
} else {
queue[rear++] = temp->left;
}
if (temp->right == NULL) {
temp->right = createNode(value);
return root;
} else {
queue[rear++] = temp->right;
}
}
return root;
}
struct Node* findDeepest(struct Node* root) {
if (root == NULL)
return NULL;
struct Node* temp = NULL;
struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
temp = queue[front++];
if (temp->left)
queue[rear++] = temp->left;
if (temp->right)
queue[rear++] = temp->right;
}
return temp;
}
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
free(root);
return NULL;
} else
return root;
}
struct Node *temp, *keyNode = NULL;
struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
temp = queue[front++];
if (temp->data == key)
keyNode = temp;
if (temp->left)
queue[rear++] = temp->left;
if (temp->right)
queue[rear++] = temp->right;
}
if (keyNode != NULL) {
struct Node* deepest = findDeepest(root);
keyNode->data = deepest->data;
front = rear = 0;
queue[rear++] = root;
while (front < rear) {
temp = queue[front++];
if (temp->left) {
if (temp->left == deepest) {
free(temp->left);
temp->left = NULL;
break;
} else {
queue[rear++] = temp->left;
}
}
if (temp->right) {
if (temp->right == deepest) {
free(temp->right);
temp->right = NULL;
break;
} else {
queue[rear++] = temp->right;
}
}
}
}
return root;
}
void inorder(struct Node* root) {
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void preorder(struct Node* root) {
if (root == NULL)
return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
void postorder(struct Node* root) {
if (root == NULL)
return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
int main() {
struct Node* root = NULL;
int choice, value;
while (1) {
printf("\n--- Binary Tree Menu ---\n");
printf("1. Insert Node\n");
printf("2. Delete Node\n");
printf("3. Inorder Traversal\n");
printf("4. Preorder Traversal\n");
printf("5. Postorder Traversal\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
root = deleteNode(root, value);
break;
case 3:
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 4:
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
break;
case 5:
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;
case 6:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice! Try again.\n");
}
}
return 0;
}