1. Illustrate a c function to add two polynomials.

Show the linked list

representation of two polynomials and its addition.
P1: 5x2+4x=2 P2: 5x+5 O/P: 5x2+9x+7

=
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a polynomial term

typedef struct PolyNode {
int coefficient; // Coefficient of the term
int exponent; // Exponent of the term
struct PolyNode* next; // Pointer to the next term
} PolyNode;

// Function to create a new polynomial term

PolyNode* createTerm(int coeff, int exp) {
PolyNode* newTerm = (PolyNode*)malloc(sizeof(PolyNode));
newTerm->coefficient = coeff;
newTerm->exponent = exp;
newTerm->next = NULL;
return newTerm;
}

// Function to insert a term at the end of the polynomial

void insertTerm(PolyNode** poly, int coeff, int exp) {
PolyNode* newTerm = createTerm(coeff, exp);

// If polynomial is empty
if (*poly == NULL) {
*poly = newTerm;
return;
}

// Find the last node

PolyNode* current = *poly;
while (current->next != NULL) {
current = current->next;
}

// Append the new term

current->next = newTerm;
}

// Function to add two polynomials

PolyNode* addPolynomials(PolyNode* poly1, PolyNode* poly2) {
PolyNode* result = NULL;
 // Traverse both polynomials
while (poly1 != NULL && poly2 != NULL) {
// If exponents are same, add coefficients
if (poly1->exponent == poly2->exponent) {
int sumCoeff = poly1->coefficient + poly2->coefficient;
if (sumCoeff != 0) {
insertTerm(&result, sumCoeff, poly1->exponent);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
// If poly1's exponent is higher, add poly1's term
else if (poly1->exponent > poly2->exponent) {
insertTerm(&result, poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
}
// If poly2's exponent is higher, add poly2's term
else {
insertTerm(&result, poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
}
}

// Add remaining terms from poly1, if any

while (poly1 != NULL) {
insertTerm(&result, poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
}

// Add remaining terms from poly2, if any

while (poly2 != NULL) {
insertTerm(&result, poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
}

return result;
}

// Function to print a polynomial

void printPolynomial(PolyNode* poly) {
if (poly == NULL) {
printf("0\n");
return;
}

while (poly != NULL) {

// Print coefficient
printf("%dx^%d", poly->coefficient, poly->exponent);
 // Print + if not the last term
if (poly->next != NULL) {
printf(" + ");
}

poly = poly->next;
}
printf("\n");
}

// Function to free polynomial memory

void freePolynomial(PolyNode* poly) {
PolyNode* temp;
while (poly != NULL) {
temp = poly;
poly = poly->next;
free(temp);
}
}

int main() {
// Create first polynomial: 5x^2 + 4x
PolyNode* poly1 = NULL;
insertTerm(&poly1, 5, 2); // 5x^2
insertTerm(&poly1, 4, 1); // 4x

// Create second polynomial: 5x + 5

PolyNode* poly2 = NULL;
insertTerm(&poly2, 5, 1); // 5x
insertTerm(&poly2, 5, 0); // 5

// Print input polynomials

printf("Polynomial 1: ");
printPolynomial(poly1);

printf("Polynomial 2: ");
printPolynomial(poly2);

// Add polynomials
PolyNode* result = addPolynomials(poly1, poly2);

// Print result
printf("Result Polynomial: ");
printPolynomial(result);

// Free memory
freePolynomial(poly1);
freePolynomial(poly2);
 freePolynomial(result);

return 0;
}

Let me break down the solution for you:

*Approach and Implementation Details:*

1. We use a linked list to represent polynomials, where each node contains:
- Coefficient
- Exponent
- Pointer to the next term

2. Key Functions:
- createTerm(): Creates a new polynomial term
- insertTerm(): Inserts a term at the end of the polynomial
- addPolynomials(): Adds two polynomials by matching and combining like terms
- printPolynomial(): Displays the polynomial
- freePolynomial(): Releases memory to prevent memory leaks

3. Addition Algorithm:
- Compare exponents of terms from both polynomials
- Add coefficients for terms with matching exponents
- Add remaining terms from either polynomial
- Skip terms with zero coefficients

*Example Run:*
- Polynomial 1: 5x^2 + 4x
- Polynomial 2: 5x + 5
- Result: 5x^2 + 9x + 5

*Time Complexity:* O(m+n), where m and n are the number of terms in the polynomials
*Space Complexity:* O(m+n) for the result polynomial

*Additional Notes:*
- The code handles polynomials of different degrees
- It dynamically allocates memory for terms
- Memory is properly freed to prevent leaks

This implementation provides a robust solution for adding polynomials using a linked list
representation, meeting the requirements of the problem statement.

2. A. Insertion of New Node as Left child

B. Insertion of New Node as Right Child
C. Insertion of New Node as Root
With The Snippet of Code Explain insertion techniques to Threaded Binary Tree.
=
#include <stdio.h>
#include <stdlib.h>

// Enum to distinguish between child and threaded links

enum LinkType {
CHILD,
THREAD
};

// Structure for Threaded Binary Tree Node

typedef struct ThreadedNode {
int data;
struct ThreadedNode* left;
struct ThreadedNode* right;
enum LinkType leftThread;
enum LinkType rightThread;
} ThreadedNode;

// Global root pointer

ThreadedNode* root = NULL;

// Function to create a new node

ThreadedNode* createNode(int value) {
ThreadedNode* newNode = (ThreadedNode*)malloc(sizeof(ThreadedNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
newNode->leftThread = CHILD;
newNode->rightThread = CHILD;
return newNode;
}

// Function to find the in-order successor

ThreadedNode* findSuccessor(ThreadedNode* ptr) {
// If right is a thread, return the right pointer
if (ptr->rightThread == THREAD)
return ptr->right;

// Find the leftmost node in right subtree

ptr = ptr->right;
while (ptr->leftThread == CHILD)
ptr = ptr->left;

return ptr;
}

// Technique 1: Insertion as Left Child

void insertAsLeftChild(ThreadedNode* parent, int value) {
// Create new node
ThreadedNode* newNode = createNode(value);

// Set left child links

newNode->left = parent->left;
newNode->leftThread = parent->leftThread;
parent->left = newNode;
parent->leftThread = CHILD;

// Update right thread of new node

if (newNode->leftThread == THREAD) {
// If previous left was a thread, update it
newNode->right = parent;
newNode->rightThread = THREAD;
}
}

// Technique 2: Insertion as Right Child

void insertAsRightChild(ThreadedNode* parent, int value) {
// Create new node
ThreadedNode* newNode = createNode(value);

// Set right child links

newNode->right = parent->right;
newNode->rightThread = parent->rightThread;
parent->right = newNode;
parent->rightThread = CHILD;

// Update left thread of new node

if (newNode->rightThread == THREAD) {
// If previous right was a thread, update it
newNode->left = parent;
newNode->leftThread = THREAD;
}
}

// Technique 3: Insertion as Root

void insertAsRoot(int value) {
// If tree is empty
if (root == NULL) {
root = createNode(value);
return;
}

// Create new root node

ThreadedNode* newRoot = createNode(value);

// Set left thread to predecessor

 newRoot->left = NULL;
newRoot->leftThread = THREAD;

// Set right thread to successor

newRoot->right = root;
newRoot->rightThread = THREAD;

// Update existing root's threads

// Find in-order predecessor of existing root
ThreadedNode* predecessor = NULL;
ThreadedNode* current = root;
while (current->leftThread == CHILD)
current = current->left;
predecessor = current->left;

// Find in-order successor of existing root

ThreadedNode* successor = findSuccessor(root);

// Update predecessor and successor threads

if (predecessor)
predecessor->right = newRoot;

// Update root
root = newRoot;
}

// In-order traversal to verify tree structure

void inorderTraversal(ThreadedNode* node) {
// Find leftmost node
while (node->leftThread == CHILD)
node = node->left;

while (node != NULL) {

printf("%d ", node->data);

// Find successor
node = findSuccessor(node);
}
}

// Main function to demonstrate insertion techniques

int main() {
// Technique 1: Insert as Left Child
root = createNode(10);
insertAsLeftChild(root, 5);

// Technique 2: Insert as Right Child

insertAsRightChild(root, 15);
 // Technique 3: Insert as Root
insertAsRoot(20);

// Verify traversal
printf("In-order Traversal: ");
inorderTraversal(root);
printf("\n");

return 0;
}

*Detailed Explanation of Threaded Binary Tree Insertion Techniques:*

1. *Data Structure Overview:*

- A Threaded Binary Tree is a special type of binary tree where null pointers are replaced with threads.
- Threads are pointers that point to the in-order predecessor or successor.
- Implemented using an enum LinkType to distinguish between child and threaded links.

2. *Insertion Technique 1: Left Child Insertion*

- insertAsLeftChild() function handles left child insertion
- Steps:
a) Create a new node
b) Preserve existing left subtree and thread links
c) Update parent's left child reference
d) Adjust thread links to maintain in-order traversal

3. *Insertion Technique 2: Right Child Insertion*

- insertAsRightChild() function handles right child insertion
- Similar to left child insertion
- Steps:
a) Create a new node
b) Preserve existing right subtree and thread links
c) Update parent's right child reference
d) Adjust thread links to maintain in-order traversal

4. *Insertion Technique 3: Root Insertion*

- insertAsRoot() function handles root insertion
- Special case handling for empty and non-empty trees
- Steps:
a) Create a new root node
b) Set threads to point to previous root and its predecessor/successor
c) Update existing tree's thread links
d) Replace root pointer

*Key Advantages:*
- Efficient in-order traversal
- Reduced space complexity
- No need for stack in traversal
*Time Complexity:*
- Insertion: O(1) for most operations
- Traversal: O(n)

*Space Complexity:*
- O(n), where n is the number of nodes

*Important Functions:*
- createNode(): Allocates memory for a new node
- findSuccessor(): Finds the in-order successor of a node
- inorderTraversal(): Demonstrates thread-based traversal

*Practical Applications:*
- Memory-efficient tree representations
- Fast in-order traversals
- Databases and indexing structures

*Potential Improvements:*
- Add error handling
- Implement deletion operations
- Create more robust thread management

3. Describe double linked list with advantages and disadvantages. Write a C

functions to delete the node from circular double linked list

= # Double Linked List Description

A double linked list is a data structure where each node contains three components:
1. Data
2. A pointer to the next node
3. A pointer to the previous node

## Advantages of Double Linked List

1. *Bidirectional Traversal*: Unlike singly linked lists, double linked lists allow traversal in both forward
and backward directions. This provides more flexibility in list manipulation.

2. *Efficient Deletion*: Nodes can be deleted more efficiently as the previous node's pointer is directly
available. This eliminates the need to traverse the entire list to find the previous node.

3. *Easy Insertion*: Inserting nodes at any position becomes easier as you have access to both next and
previous node pointers.

4. *Reversing the List*: Reversing a double linked list is simpler compared to a singly linked list, as you
can easily change the next and previous pointers.

## Disadvantages of Double Linked List

1. *Extra Memory Overhead*: Each node requires an additional pointer (previous pointer), which
increases memory consumption compared to singly linked lists.

2. *Complex Implementation*: The implementation is more complex due to the need to manage two
pointers for each node.

3. *Increased Complexity in Insertion and Deletion*: More pointer manipulations are required during
node operations, which can lead to more complex code.

Now, I'll write the C functions to delete a node from a circular double linked list:
c
// Structure for Circular Double Linked List Node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// Function to delete a node from Circular Double Linked List

struct Node* deleteNode(struct Node* head, int key) {
// If list is empty
if (head == NULL) {
return NULL;
}

struct Node* current = head;

struct Node* toDelete = NULL;

// Search for the node to be deleted

do {
if (current->data == key) {
toDelete = current;
break;
}
current = current->next;
} while (current != head);

// If node not found

if (toDelete == NULL) {
return head;
}

// If list has only one node

if (current->next == current) {
free(current);
return NULL;
}

// If node to delete is head

 if (toDelete == head) {
head = head->next;
}

// Adjust the links

toDelete->prev->next = toDelete->next;
toDelete->next->prev = toDelete->prev;

// Free the memory

free(toDelete);

return head;
}

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Function to insert a node at the end of Circular Double Linked List

struct Node* insertAtEnd(struct Node* head, int data) {
struct Node* newNode = createNode(data);

// If list is empty
if (head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}

// Insert at the end

newNode->prev = head->prev;
newNode->next = head;
head->prev->next = newNode;
head->prev = newNode;

return head;
}

// Function to print the Circular Double Linked List

void printList(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
 struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}

Let me break down the key aspects of the implementation:

1. *deleteNode Function*:
- Searches for the node with the given key in the circular list
- Handles different scenarios:
* Empty list
* Single node list
* Deleting the head node
* Deleting a node in the middle or end

2. *Time Complexity*:
- Searching: O(n)
- Deletion: O(1) once the node is found

3. *Space Complexity*:
- O(1) extra space

Example usage would look like:

c
struct Node* head = NULL;
head = insertAtEnd(head, 10);
head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);

printf("Original List: ");

printList(head);

head = deleteNode(head, 20);

printf("List after deleting 20: ");

printList(head);

4. State a C routine to traverse the binary tree

A. Preorder traversal
B. Post order traversal
=
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a binary tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// a) Preorder Traversal (Root -> Left -> Right)

void preorderTraversal(struct Node* root) {
if (root == NULL)
return;

// First, print the root (current node)

printf("%d ", root->data);

// Then, recursively traverse left subtree

preorderTraversal(root->left);

// Finally, recursively traverse right subtree

preorderTraversal(root->right);
}

// b) Postorder Traversal (Left -> Right -> Root)

void postorderTraversal(struct Node* root) {
if (root == NULL)
return;

// First, recursively traverse left subtree

postorderTraversal(root->left);

// Then, recursively traverse right subtree

postorderTraversal(root->right);

// Finally, print the root (current node)

printf("%d ", root->data);
}

// Example usage
int main() {
 // Create a sample binary tree
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Preorder Traversal: ");

preorderTraversal(root);
printf("\n");

printf("Postorder Traversal: ");

postorderTraversal(root);
printf("\n");

return 0;
}

Let me explain the code:

1. We define a Node structure to represent each node in the binary tree, containing:
- data: the value stored in the node
- left: pointer to the left child
- right: pointer to the right child

2. Preorder Traversal (a):

- Visit the root node first
- Then traverse the left subtree
- Finally traverse the right subtree
- Order: Root -> Left -> Right

3. Postorder Traversal (b):

- First traverse the left subtree
- Then traverse the right subtree
- Finally visit the root node
- Order: Left -> Right -> Root
The main function creates a sample binary tree and demonstrates both traversal methods:

1
/ \
2 3
/\
4 5

For this tree:

- Preorder traversal would print: 1 2 4 5 3
- Postorder traversal would print: 4 5 2 3 1
The time complexity for both traversals is O(n), where n is the number of nodes in the tree, as each node is
visited exactly once