Siyam241-15-758

T
Siyam241-15-758

ask 1: Complete Binary Tree Operations

Objective: Implement and write insert and delete operations as functions on a
complete binary tree in two representations:
1. Linked-list based complete binary tree
2. Array-based complete binary tree
Instructions
1. Insertion:
o Insert nodes level-by-level to maintain the structure of a
complete binary tree.
o Follow the rules of a complete binary tree where all levels are filled
except possibly the last, and the last level nodes are filled from left to
right.
2. Deletion:
o Implement deletion of nodes while maintaining completeness.
o Delete the last node (rightmost) at the last level of the tree to
prevent the tree from being incomplete.
3. Testing and Visualization:
o Provide at least three test cases for each implementation (linked-list
and array).
o For each test case, draw the structure of the binary tree before and
after each operation to demonstrate correctness.
Siyam241-15-758

1. Here is the Linked-list based complete binary tree

#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;
}

//Insertion
void insert(struct Node** root, int data)
{
if (*root == NULL)
{
*root = createNode(data);
return;
Siyam241-15-758

struct Node* temp = *root;

struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = temp;
while (front < rear)
{
struct Node* current = queue[front++];
if (current->left == NULL)
{
current->left = createNode(data);
return;
}
else
{
queue[rear++] = current->left;
}
if (current->right == NULL)
{
current->right = createNode(data);
return;
}
else
Siyam241-15-758

{
queue[rear++] = current->right;
}
}
}

// Deletion:
void deleteLastNode(struct Node** root) {
if (*root == NULL) {
printf("Tree is empty!\n");
return;
}
struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = *root;
struct Node* parent = NULL;
struct Node* lastNode = NULL;
while (front < rear) {
struct Node* current = queue[front++];
lastNode = current;
if (current->left) queue[rear++] = current->left;
if (current->right) queue[rear++] = current->right;
}
if (lastNode == *root) {
free(lastNode);
Siyam241-15-758

*root = NULL;
return;
}
front = 0;
rear = 0;
queue[rear++] = *root;
while (front < rear) {
struct Node* current = queue[front++];
if (current->left == lastNode) {
parent = current;
parent->left = NULL;
break;
} else if (current->right == lastNode) {
parent = current;
parent->right = NULL;
break;
}
if (current->left) queue[rear++] = current->left;
if (current->right) queue[rear++] = current->right;
}

free(lastNode);
}
Siyam241-15-758

//Testing and Visualization:

void printLevelOrder(struct Node* root)

{
if (root == NULL) return;
struct Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear)
{
struct Node* current = queue[front++];
printf("%d ", current->data);

if (current->left) queue[rear++] = current->left;

if (current->right) queue[rear++] = current->right;
}
printf("\n");
}
Siyam241-15-758

int main()
{
struct Node* root = NULL;
insert(&root, 10);
insert(&root, 20);
insert(&root, 30);
insert(&root, 40);
insert(&root, 50);
printf("Level order traversal after insertions: ");
printLevelOrder(root);
printf("Deleting the last node...\n");
deleteLastNode(&root);
printf("Level order traversal after deleting the last node: ");
printLevelOrder(root);

return 0;
}
Siyam241-15-758

Before Deletion:
After inserting nodes 10, 20, 30, 40, 50, the tree looks like this:
markdown
Copy code
10
/ \
20 30
/ \
40 50
After Deleting the Last Node:
The last node 50 (rightmost at the last level) will be deleted, so after the
deletion:
markdown
Copy code
10
/ \
20 30
/
40
Conclusion:
This code correctly implements the deletion of the last node (rightmost node at
the last level) in a complete binary tree. The tree remains complete after the
deletion, and the operations maintain the binary tree's structure. This approach
ensures that the tree's completeness is preserved after each deletion operation.
Siyam241-15-758

2. Array-based complete binary tree

In an array-based representation, the tree is represented as an array, where the
root is at index 0. For any node at index i:
 Left child is at index 2*i + 1
 Right child is at index 2*i + 2
 Parent node is at index (i-1) / 2
Code for Array-based Complete Binary Tree:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
void insert(int tree[], int* size, int data) {
if (*size < MAX_SIZE) {
tree[*size] = data;
(*size)++;
}
}
void delete(int tree[], int* size) {
if (*size > 0) {
(*size)--;
}
}
void printLevelOrder(int tree[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", tree[i]);
Siyam241-15-758

}
printf("\n");
}
int main() {
int tree[MAX_SIZE];
int size = 0;
insert(tree, &size, 10);
insert(tree, &size, 20);
insert(tree, &size, 30);
insert(tree, &size, 40);
insert(tree, &size, 50);
printf("Level order traversal after insertions: ");
printLevelOrder(tree, size);
delete(tree, &size);
printf("Level order traversal after deletion: ");
printLevelOrder(tree, size);

return 0;
}
Siyam241-15-758

Array version:
1. Insert 10 → 20 → 30 → 40 → 50
o Tree structure:
[10, 20, 30, 40, 50]
After deletion:
[10, 20, 30, 40]

Task 2: Linked-list Based N-ary Tree Implementation

Objective: Implement a linked-list-based N-ary tree that can
dynamically add children to any node.
Instructions
1. Implementation:
o Use a linked-list-based structure where each node can
have N children.
o Allow users to specify the number of children N for the tree
and dynamically add children nodes to any given parent (e.g.,
Left link can indicate parent-child relations, and right link can
specify the sibling).
2. Testing and Visualization:
o Provide three test cases where each test demonstrates
different aspects of adding children nodes, including adding
multiple children to one node and creating multiple levels in
the tree.
o Draw the structure of the N-ary tree after each operation to
illustrate its structure
Siyam241-15-758

Implementation Steps:
1. Node Creation: Create a new node with a given value.
2. Add Children: Dynamically add children nodes to any given parent node.
3. Print Tree: We will implement a function to print the tree structure to
visualize it.
4. Test Cases: Demonstrate adding multiple children to a node and creating
multiple levels in the tree.
Code Implementation
#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;
}
void addChild(struct Node* parent, struct Node* child) {
if (parent == NULL) {
printf("Parent node is NULL!\n");
Siyam241-15-758

return;
}
if (parent->left == NULL) {
parent->left = child;
} else {
struct Node* temp = parent->left;
while (temp->right != NULL) {
temp = temp->right;
}
temp->right = child;
}
}
void printTree(struct Node* root, int level) {
if (root == NULL) return;

for (int i = 0; i < level; i++) printf(" ");

printf("%d\n", root->data);
printTree(root->left, level + 1);

printTree(root->right, level);
}
int main() {

struct Node* root = createNode(1);

Siyam241-15-758

printf("Test Case 1: Adding children to root node\n");

struct Node* child1 = createNode(2);
struct Node* child2 = createNode(3);
struct Node* child3 = createNode(4);
addChild(root, child1);
addChild(root, child2);
addChild(root, child3);
printf("Tree structure after adding children to root node:\n");
printTree(root, 0);
printf("\nTest Case 2: Adding children to node 3 (one of the child nodes)\n");
struct Node* child2_1 = createNode(5);
struct Node* child2_2 = createNode(6);
addChild(child2, child2_1);
addChild(child2, child2_2);

printf("Tree structure after adding children to node 3:\n");

printTree(root, 0);
printf("\nTest Case 3: Adding children to node 2 (child1)\n");
struct Node* child1_1 = createNode(7);
struct Node* child1_2 = createNode(8);
addChild(child1, child1_1);
addChild(child1, child1_2);
printf("Tree structure after adding children to node 2:\n");
printTree(root, 0);
Siyam241-15-758

return 0;
}
Explanation of the Code:
1. Node Structure:
o Each node is defined by the struct Node which contains:
 data: The value stored in the node.
 left: Pointer to the first child.
 right: Pointer to the next sibling.
2. Creating a Node:
o The createNode function creates a new node, initializes it with the given data,
and sets both left and right pointers to NULL.
3. Adding a Child:
o The addChild function adds a child node to a given parent node.
 If the parent node has no children (left == NULL), the child is simply
added as the first child.
 If the parent already has children, the function iterates through the list of
children using the right pointer and attaches the new child at the end of
the sibling list.
4. Printing the Tree:
o The printTree function performs a recursive level-order traversal to print the
tree in a readable structure. The level parameter is used to determine the
indentation for each node, indicating its depth in the tree.
Test Cases:
Test Case 1: Add Multiple Children to the Root Node
 Expected Output:
Tree structure after adding children to root node:
1
2
Siyam241-15-758

3
4
Test Case 2: Add Children to One of the Child Nodes
 Expected Output:
Tree structure after adding children to node 3:
1
2
3
5
6
4
Test Case 3: Add Children to Another Level
 Expected Output:
Tree structure after adding children to node 2:
1
2
7
8
3
5
6
4
Visualization of the Tree:
1. After Test Case 1:
1
├── 2
├── 3
Siyam241-15-758

└── 4
2. After Test Case 2:
1
├── 2
└── 3
├── 5
└── 6
└── 4
3. After Test Case 3:
1
├── 2
│ ├── 7
│ └── 8
└── 3
├── 5
└── 6
└── 4
Conclusion:
This implementation provides a flexible way to create an N-ary tree where each node can have
up to N children. The structure of the tree is managed using a linked-list-based representation
where each node has a left pointer to its first child and a right pointer to its next sibling. The
addChild function dynamically adds children to any node, allowing users to create complex
hierarchical structures. The printTree function helps visualize the tree at any stage of
construction.