Question 1

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

// Function to find the next greater element

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* ans = (int*)malloc(nums1Size * sizeof(int));
int* stack = (int*)malloc(nums2Size * sizeof(int));
int top = -1;
int* map = (int*)malloc(nums2Size * sizeof(int));

// Initialize the map with -1

for (int i = 0; i < nums2Size; i++) {
map[i] = -1;
}

// Iterate through nums2 to build the map

for (int i = 0; i < nums2Size; i++) {
while (top >= 0 && nums2[stack[top]] < nums2[i]) {
map[stack[top--]] = nums2[i];
}
stack[++top] = i;
}

// Build the answer array

for (int i = 0; i < nums1Size; i++) {
for (int j = 0; j < nums2Size; j++) {
 if (nums1[i] == nums2[j]) {
ans[i] = map[j];
break;
}
}
}

free(stack);
free(map);
return ans;
}

int main() {
int nums1[] = {4, 1, 2};
int nums2[] = {1, 3, 4, 2};
int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
int nums2Size = sizeof(nums2) / sizeof(nums2[0]);

int* ans = nextGreaterElement(nums1, nums1Size, nums2, nums2Size);

// Print the answer array

for (int i = 0; i < nums1Size; i++) {
printf("%d ", ans[i]);
}

free(ans);
return 0;
}
Question 2:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Structure to represent a dynamic stack

typedef struct {
int* elements;
int top;
int capacity;
} Stack;

// Function to create a new dynamic stack

Stack* createStack(int initialCapacity) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->elements = (int*)malloc(initialCapacity * sizeof(int));
stack->top = -1;
stack->capacity = initialCapacity;
return stack;
}

// Function to push an element onto the stack

void push(Stack* stack, int element) {
if (stack->top == stack->capacity - 1) {
// Resize the stack if it's full
stack->capacity *= 2;
stack->elements = (int*)realloc(stack->elements, stack->capacity * sizeof(int));
}
 stack->elements[++stack->top] = element;
}

// Function to pop an element from the stack

int pop(Stack* stack) {
if (stack->top == -1) {
printf("Stack is empty\n");
exit(1);
}
return stack->elements[stack->top--];
}

// Function to evaluate the postfix expression

int evaluatePostfix(char* expression) {
Stack* stack = createStack(10);
char* token = strtok(expression, " ");
int operand1, operand2;

while (token != NULL) {

if (strcmp(token, "+") == 0) {
operand2 = pop(stack);
operand1 = pop(stack);
push(stack, operand1 + operand2);
} else if (strcmp(token, "-") == 0) {
operand2 = pop(stack);
operand1 = pop(stack);
push(stack, operand1 - operand2);
} else if (strcmp(token, "*") == 0) {
operand2 = pop(stack);
 operand1 = pop(stack);
push(stack, operand1 * operand2);
} else if (strcmp(token, "/") == 0) {
operand2 = pop(stack);
operand1 = pop(stack);
push(stack, operand1 / operand2);
} else {
push(stack, atoi(token));
}
token = strtok(NULL, " ");
}

int result = pop(stack);

free(stack->elements);
free(stack);
return result;
}

int main() {
char expression[100];
printf("Enter the postfix expression: ");
fgets(expression, sizeof(expression), stdin);
expression[strcspn(expression, "\n")] = 0; // Remove the newline character

int result = evaluatePostfix(expression);

printf("The result of the postfix expression is: %d\n", result);

return 0;
}
Question 3:
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a node in the queue

typedef struct Node {
int data;
struct Node* next;
} Node;

// Structure to represent the queue

typedef struct {
Node* front;
Node* rear;
} Queue;

// Function to create a new node

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

// Function to enqueue an element into the queue

void enqueue(Queue* queue, int data) {
Node* node = createNode(data);
if (queue->rear == NULL) {
 queue->front = queue->rear = node;
} else {
queue->rear->next = node;
queue->rear = node;
}
}

// Function to dequeue an element from the queue

int dequeue(Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
exit(1);
}
int data = queue->front->data;
Node* temp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return data;
}

// Function to reverse the queue using a stack

void reverseQueue(Queue* queue) {
// Create a stack to store the elements
int stack[100];
int top = -1;
 // Dequeue all elements from the queue and push them onto the stack
while (queue->front != NULL) {
stack[++top] = dequeue(queue);
}

// Pop all elements from the stack and enqueue them back into the queue
while (top != -1) {
enqueue(queue, stack[top--]);
}
}

int main() {
Queue queue;
queue.front = queue.rear = NULL;

int N;
printf("Enter the number of elements in the queue: ");
scanf("%d", &N);

printf("Enter the elements of the queue: ");

for (int i = 0; i < N; i++) {
int data;
scanf("%d", &data);
enqueue(&queue, data);
}

reverseQueue(&queue);

printf("Reversed queue: ");

 while (queue.front != NULL) {
printf("%d ", dequeue(&queue));
}
printf("\n");

return 0;
}

Question 4:
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a node in the binary tree

typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;

// Function to create a new node

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

// Function to construct the binary tree from inorder and postorder traversals
Node* constructTree(int in[], int post[], int inStart, int inEnd, int* postIndex) {
 if (inStart > inEnd) {
return NULL;
}

// Create a new node with the last element of the postorder traversal
Node* node = createNode(post[(*postIndex)--]);

// Find the index of the node in the inorder traversal

int index = -1;
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == node->data) {
index = i;
break;
}
}

// Recursively construct the right and left subtrees

node->right = constructTree(in, post, index + 1, inEnd, postIndex);
node->left = constructTree(in, post, inStart, index - 1, postIndex);

return node;
}

// Function to print the preorder traversal of the binary tree

void printPreorder(Node* node) {
if (node == NULL) {
return;
}
 printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}

int main() {
int n = 7; // Corrected size of the array
int in[] = {4, 8, 2, 5, 1, 3, 7};
int post[] = {8, 4, 5, 2, 7, 3, 1};

int postIndex = n - 1;
Node* root = constructTree(in, post, 0, n - 1, &postIndex);

printf("Preorder traversal: ");

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

return 0;
}

Question 5:
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a node in the binary tree

typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;

// Function to create a new node

Node* createNode(int data) {
if (data == -1) // Using -1 to represent NULL in the array
return NULL;
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}

// Function to construct the binary tree from the level order array
Node* constructTree(int arr[], int n) {
if (n == 0 || arr[0] == -1) {
return NULL;
}

Node** queue = (Node**)malloc(n * sizeof(Node*));

int front = 0, rear = 0;

Node* root = createNode(arr[0]);

queue[rear++] = root;

for (int i = 1; i < n; i += 2) {

Node* parent = queue[front++];

if (arr[i] != -1) {
parent->left = createNode(arr[i]);
 queue[rear++] = parent->left;
}

if (i + 1 < n && arr[i + 1] != -1) {

parent->right = createNode(arr[i + 1]);
queue[rear++] = parent->right;
}
}

free(queue);
return root;
}

// Function to print the right side view of the binary tree

void printRightSideView(Node* root) {
if (root == NULL) {
return;
}

Node** queue = (Node**)malloc(100 * sizeof(Node*)); // Assuming a maximum tree size

int front = 0, rear = 0;

queue[rear++] = root;

while (front < rear) {

int levelSize = rear - front;
Node* rightMost = NULL;

for (int i = 0; i < levelSize; i++) {

 Node* currentNode = queue[front++];

if (currentNode->left != NULL) {
queue[rear++] = currentNode->left;
}

if (currentNode->right != NULL) {
queue[rear++] = currentNode->right;
}

rightMost = currentNode;
}

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

}

printf("\n");
free(queue);
}

int main() {
int arr[] = {1,2,3,4,5,NULL,7,8};
int n = sizeof(arr) / sizeof(arr[0]);

Node* root = constructTree(arr, n);

printf("Right side view of the tree: ");

printRightSideView(root);
 return 0;
}