Data Structure using C - Question Paper
Time: 3 Hours
Maximum Marks: 100
Section A: Descriptive Questions (20 Marks)
Question 1 (2 marks):
Explain the concept of time complexity and space complexity in algorithm analysis. Provide a brief example of each.
Ans. Time Complexity and Space Complexity:
- Time complexity refers to the amount of time an algorithm takes to complete as a function of the input size.
- Space complexity is the amount of memory space required by an algorithm concerning the input size.
- Example: Linear Search has a time complexity of O(n), and Bubble Sort has a space complexity of O(1).
Question 2 (2 marks):
Define the term "Data Structure." Discuss the importance of selecting an appropriate data structure in programming.
Ans. Data Structure:
- A data structure is a way of organizing and storing data to perform operations efficiently.
- Choosing the right data structure is crucial as it impacts the efficiency of operations.
Question 3 (2 marks):
Differentiate between an array and a linked list. In what scenarios would you prefer using one over the other?
Ans. Array vs. Linked List:
- Arrays are contiguous memory locations, while linked lists use pointers.
- Arrays are preferable when direct access is needed, and linked lists are suitable for dynamic size and frequent insertions/deletions.
Question 4 (2 marks):
What is recursion, and how does it work in programming? Provide a simple example of a recursive function.
Ans. Recursion:
- Recursion is a programming technique where a function calls itself.
- Example: Factorial function: `
int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }`
Question 5 (2 marks):
Explain the purpose of the following terms in the context of trees:
a. Root
b. Leaf
c. Parent
d. Child
Ans. Tree Terminology:
- a. Root: The topmost node.
- b. Leaf: A node with no children.
- c. Parent: A node with children.
- d. Child: A node connected to a parent.
Question 6 (2 marks):
Explain the concept of Big O notation in algorithm analysis. How does it help in evaluating the efficiency of algorithms?
Ans. Big O Notation:
- Big O notation expresses the upper bound of an algorithm's time complexity.
- Helps compare algorithms and predict their behavior with large inputs.
Question 7 (2 marks):
Define the term "Abstract Data Type (ADT)." Provide an example of an ADT and explain its characteristics.
Ans. Abstract Data Type (ADT):
- ADT is a high-level description of a set of operations without specifying the implementation.
- Example: Stack - supports push, pop, and isEmpty operations.
Question 8 (2 marks):
Differentiate between a stack and a queue. Provide examples of real-world scenarios where each data structure is applicable.
Ans. Stack vs. Queue:
- Stack follows Last In First Out (LIFO), while Queue follows First In First Out (FIFO).
- Stack is suitable for function call tracking, and Queue is used in task scheduling.
Question 9 (2 marks):
Discuss the importance of pointers in C programming, particularly in the context of data structures.
Ans. Pointers in C:
- Pointers store the memory address of variables. In data structures, they facilitate dynamic memory allocation and efficient traversal.
Question 10 (2 marks):
Explain the concept of "tree traversal" in binary trees. Provide examples of pre-order and in-order traversal.
Ans. Tree Traversal:
- Pre-order: Root, Left, Right
- In-order: Left, Root, Right
Section B: Algorithm Design and Analysis (50 Marks)
Question 1 (5 marks):
Describe the process of dynamic memory allocation and deallocation in C. Highlight the differences between malloc() and free().
Ans. Dynamic memory allocation in C involves using functions like malloc() to request memory during program execution. The process typically consists of the following steps:
- Allocation: Use
malloc(size) to allocate a block of memory of the specified size. - Checking for Allocation Success: Verify if the allocation was successful by checking if the returned pointer is not NULL.
- Usage: Utilize the allocated memory for storing data.
- Deallocation: Use
free(pointer) to release the allocated memory when it's no longer needed.
Differences between malloc() and free():
malloc(size): Allocates a specified amount of memory and returns a pointer to the first byte.free(pointer): Releases the memory pointed to by the given pointer, making it available for reuse.
Question 2 (5 marks):
Discuss the significance of hash tables in data structures. Provide an example illustrating the use of a hash table.
Ans. Hash tables are crucial data structures that provide efficient data retrieval and storage. They offer constant-time average complexity for search, insert, and delete operations. A hash table consists of an array and a hash function that maps keys to indices in the array.
Example:
Consider a system where you want to store and retrieve the contact details of individuals using their phone numbers. In this scenario, a hash table can be employed, where the phone numbers serve as keys. The hash function could be based on the last few digits of the phone number, and the array would store the corresponding contact details.
Question 3 (5 marks):
Explain the concept of a doubly-linked list. Provide code snippets for inserting and deleting nodes in a doubly-linked list.
Ans. A doubly-linked list is a linked list in which each node contains a data element and two pointers, one pointing to the next node (next pointer) and another pointing to the previous node (prev pointer).
Code snippets:
// Node structure for doubly-linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Insertion at the end
void insertEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
newNode->data = newData;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
while (last->next != NULL)
last = last->next;
last->next = newNode;
newNode->prev = last;
}
// Deletion by key
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
while (temp != NULL && temp->data != key)
temp = temp->next;
if (temp == NULL) return;
if (temp->prev != NULL)
temp->prev->next = temp->next;
if (temp->next != NULL)
temp->next->prev = temp->prev;
free(temp);
}
Question 4 (5 marks):
Compare and contrast breadth-first search (BFS) and depth-first search (DFS) algorithms. Offer examples of situations where each is preferable.
Ans. Breadth-First Search (BFS):
- Traversal Order: Level-wise, exploring all neighbors at the current level before moving to the next level.
- Memory Usage: More memory-intensive due to the need to store all nodes at the current level.
- Implementation: Typically implemented using a queue.
Depth-First Search (DFS):
- Traversal Order: Goes as deep as possible before backtracking.
- Memory Usage: Less memory-intensive as it explores as far as possible along each branch before backtracking.
- Implementation: Typically implemented using recursion or a stack.
Comparison:
- Space Complexity: BFS generally requires more memory than DFS.
- Completeness: BFS is complete for finite graphs; DFS might get stuck in infinite loops.
- Optimality: BFS is optimal for finding the shortest path in an unweighted graph, while DFS might not be.
Preferable Situations:
- BFS: Useful for finding the shortest path in an unweighted graph, network broadcasting, and puzzles with multiple solutions.
- DFS: Suitable for topological sorting, detecting cycles in a graph, and puzzles with a single solution.
Question 5 (5 marks):
Discuss the concept of a priority queue. Provide a real-world example where a priority queue would be beneficial.
Ans. Priority Queue:
- A data structure that stores elements with associated priorities.
- Elements with higher priorities are served before elements with lower priorities.
Real-world Example:
Consider an emergency room where patients are prioritized based on the severity of their condition. A priority queue could be employed to efficiently manage patient queues. Patients with higher medical urgency (higher priority) would be treated before those with lower urgency.
Question 6 (5 marks):
Discuss the role of the "malloc" function in dynamic memory allocation in C. Provide an example of its usage.
Ans. malloc Function:
malloc (Memory Allocation) is a standard library function in C used for dynamic memory allocation.- It allocates a specified number of bytes and returns a pointer to the beginning of the allocated memory.
Example Usage:
#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr;
int n = 5;
// Allocate memory for an array of 5 integers
arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed!");
return 1; // Error code
}
// Use the allocated memory as needed
// Deallocate the memory when done
free(arr);
return 0;
}
Question 7 (5 marks):
Explain the concept of hashing. How does collision resolution work in hash tables? Provide an example.
Ans. Hashing Concept:
- Hashing is a technique that maps data to a fixed-size array called a hash table.
- It uses a hash function to compute an index into the array where the desired information can be found.
Collision Resolution:
- Collision occurs when two different keys hash to the same index.
- Collision resolution techniques include chaining (using linked lists at each array index) and open addressing (finding the next open slot).
Example:
Consider a hash table storing employee information. The hash function could be based on employee IDs, and collision resolution might involve chaining. If two employees have the same hash, their information is stored in a linked list at that hash index.
Question 8 (5 marks):
Design a C program to implement a circular linked list. Include functions for insertion and deletion of nodes.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end
void insertEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
newNode->data = newData;
newNode->next = *head;
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
return;
}
while (last->next != *head)
last = last->next;
last->next = newNode;
}
// Function to delete a node by key
void deleteNode(struct Node** head, int key) {
if (*head == NULL)
return;
struct Node* current = *head, *prev = NULL;
while (current->data != key) {
prev = current;
current = current->next;
if (current == *head)
return; // Key not found, exit to avoid infinite loop
}
if (current->next == *head && prev == NULL) {
free(current);
*head = NULL;
return;
}
if (prev == NULL)
*head = current->next;
prev->next = current->next;
free(current);
}
// Function to display the circular linked list
void displayList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
int main() {
struct Node* head = NULL;
insertEnd(&head, 1);
insertEnd(&head, 2);
insertEnd(&head, 3);
insertEnd(&head, 4);
printf("Circular Linked List: ");
displayList(head);
deleteNode(&head, 3);
printf("Circular Linked List after deletion: ");
displayList(head);
return 0;
}
Question 9 (5 marks):
Compare the time complexities of linear search and binary search algorithms. In what scenarios would you prefer one over the other?
Ans. Linear Search:
- Time Complexity: O(n) - linear in the size of the array.
- Suitable for small datasets or unsorted arrays.
Binary Search:
- Time Complexity: O(log n) - logarithmic, applicable to sorted arrays.
- Preferable for large sorted datasets, as it significantly reduces the number of comparisons.
Scenario Preference:
- Use Linear Search when the data is unordered, or the dataset is small.
- Use Binary Search when dealing with large, sorted datasets, as it offers faster search times.
Question 10 (5 marks):
Discuss the concept of a heap in the context of priority queues. How is a heap represented, and what operations can be performed on it?
Ans. Heap Concept:
- A heap is a specialized tree-based data structure that satisfies the heap property.
- In a max heap, the key of each node is greater than or equal to the keys of its children.
- In a min heap, the key of each node is less than or equal to the keys of its children.
Representation:
- Heaps are commonly represented using arrays. The root of the heap is at index 0, and for any element at index
i, its left child is at 2i + 1 and the right child is at 2i + 2.
Operations:
- Insertion: Add a new element to the heap while maintaining the heap property.
- Deletion: Remove the root element (max or min) and adjust the heap.
- Heapify: Convert an array into a heap, ensuring the heap property.
Example:
Consider a max heap:
9
/ \
7 5
/ \
3 4
Section C: Programming and Problem Solving(Any Five) (30 Marks)
Question 1 (6 marks):
Implement a C program to perform sorting on a doubly-linked list. Explain the logic behind your implementation.
Ans. #include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to insert a new node at the end
void insertEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
newNode->data = newData;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
while (last->next != NULL)
last = last->next;
last->next = newNode;
newNode->prev = last;
}
// Function to perform sorting on a doubly-linked list using bubble sort
void sortDoublyLinkedList(struct Node** head) {
if (*head == NULL || (*head)->next == NULL)
return;
struct Node *i, *j;
int temp;
for (i = *head; i->next != NULL; i = i->next) {
for (j = i->next; j != NULL; j = j->next) {
if (i->data > j->data) {
// Swap data
temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}
}
// Function to display the doubly-linked list
void displayList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly-linked list
insertEnd(&head, 3);
insertEnd(&head, 1);
insertEnd(&head, 4);
insertEnd(&head, 2);
printf("Original Doubly-Linked List: ");
displayList(head);
// Sort the doubly-linked list
sortDoublyLinkedList(&head);
printf("Sorted Doubly-Linked List: ");
displayList(head);
return 0;
}
Explanation:
- The program uses the bubble sort algorithm to sort the doubly-linked list.
- The
sortDoublyLinkedList function compares adjacent elements and swaps them if they are in the wrong order. - The sorting process is repeated until the entire list is sorted.
- The
displayList function is used to print the elements of the doubly-linked list.
Question 2 (6 marks):
Design and implement a binary search tree (BST) in C. Include functions for insertion, deletion, and searching.
Ans. #include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int key) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert a key into the BST
struct Node* insertNode(struct Node* root, int key) {
if (root == NULL)
return createNode(key);
if (key < root->data)
root->left = insertNode(root->left, key);
else if (key > root->data)
root->right = insertNode(root->right, key);
return root;
}
// Function to find the minimum value node in a BST
struct Node* findMin(struct Node* node) {
while (node->left != NULL)
node = node->left;
return node;
}
// Function to delete a key from the BST
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL)
return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
// Node with two children
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function to search for a key in the BST
struct Node* searchNode(struct Node* root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return searchNode(root->left, key);
else
return searchNode(root->right, key);
}
// Function to print the inorder traversal of the BST
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
struct Node* root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
printf("Searching for 40
Question 3 (6 marks):
Write a program in C to evaluate a postfix expression using a stack. Explain the algorithm and include error handling mechanisms.
Ans. #include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
struct Stack {
int top;
int items[MAX_SIZE];
};
// Function to initialize an empty stack
void initialize(struct Stack* stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int value) {
if (stack->top == MAX_SIZE - 1) {
printf("Error: Stack Overflow\n");
exit(1);
}
stack->items[++stack->top] = value;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Error: Stack Underflow\n");
exit(1);
}
return stack->items[stack->top--];
}
// Function to evaluate a postfix expression
int evaluatePostfix(char postfix[]) {
struct Stack stack;
initialize(&stack);
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i]))
push(&stack, postfix[i] - '0');
else {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
switch (postfix[i]) {
case '+': push(&stack, operand1 + operand2); break;
case '-': push(&stack, operand1 - operand2); break;
case '*': push(&stack, operand1 * operand2); break;
case '/':
if (operand2 == 0) {
printf("Error: Division by zero\n");
exit(1);
}
push(&stack, operand1 / operand2);
break;
default:
printf("Error: Invalid operator\n");
exit(1);
}
}
}
return pop(&stack);
}
int main() {
char postfixExpression[] = "23*5+";
int result = evaluatePostfix(postfixExpression);
printf("Result of the postfix expression: %d\n", result);
return 0;
}
Explanation:
- The program uses a stack to evaluate a postfix expression.
- It iterates through each character in the postfix expression.
- If the character is a digit, it is pushed onto the stack.
- If the character is an operator, two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
- Error handling mechanisms are included for stack overflow, stack underflow, division by zero, and invalid operators.
Question 4 (6 marks):
Given a graph represented as an adjacency matrix, write a C program to perform a depth-first search (DFS). Provide the output for a sample graph.
Ans. #include <stdio.h>
#define MAX_VERTICES 5
int visited[MAX_VERTICES] = {0};
void depthFirstSearch(int graph[MAX_VERTICES][MAX_VERTICES], int vertex) {
printf("%d ", vertex);
visited[vertex] = 1;
for (int i = 0; i < MAX_VERTICES; i++) {
if (graph[vertex][i] == 1 && !visited[i])
depthFirstSearch(graph, i);
}
}
int main() {
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
printf("Depth-First Search starting from vertex 0: ");
depthFirstSearch(graph, 0);
return 0;
}
Output:
Depth-First Search starting from vertex 0: 0 1 3 2 4
Explanation:
- The program performs depth-first search (DFS) on a sample graph represented as an adjacency matrix.
- It starts the traversal from vertex 0 and prints the vertices in the order they are visited.
- The
visited array is used to keep track of visited vertices to avoid revisiting them during the traversal. - The output represents the order of vertices visited during the depth-first search.
Question 5 (6 marks):
Design and implement a stack using an array in C. Include functions for push, pop, and display.
Ans. #include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int top;
int items[MAX_SIZE];
};
// Function to initialize an empty stack
void initialize(struct Stack* stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Error: Stack Overflow\n");
exit(1);
}
stack->items[++stack->top] = value;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Error: Stack Underflow\n");
exit(1);
}
return stack->items[stack->top--];
}
// Function to display the stack
void displayStack(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->items[i]);
}
printf("\n");
}
int main() {
struct Stack stack;
initialize(&stack);
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
displayStack(&stack);
int popped = pop(&stack);
printf("Popped element: %d\n", popped);
displayStack(&stack);
return 0;
}
Explanation:
- The program demonstrates the implementation of a stack using an array in C.
- It includes functions for initializing, checking if the stack is empty or full, pushing an element, popping an element, and displaying the stack.
- Error handling mechanisms are included for stack overflow and underflow.
Question 6 (6 marks):
Design and implement a stack using an array in C. Include functions for push, pop, and display.
Ans. #include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Queue {
int front, rear, size;
int items[MAX_SIZE];
};
// Function to initialize an empty queue
void initialize(struct Queue* queue) {
queue->front = queue->rear = -1;
queue->size = 0;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->size == 0;
}
// Function to check if the queue is full
int isFull(struct Queue* queue) {
return queue->size == MAX_SIZE;
}
// Function to enqueue an element
void enqueue(struct Queue* queue, int value) {
if (isFull(queue)) {
printf("Error: Queue Overflow\n");
exit(1);
}
if (isEmpty(queue))
queue->front = 0;
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->items[queue->rear] = value;
queue->size++;
}
// Function to dequeue an element
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Error: Queue Underflow\n");
exit(1);
}
int frontItem = queue->items[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE;
queue->size--;
if (isEmpty(queue))
initialize(queue);
return frontItem;
}
// Function to display the queue
void displayQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return;
}
printf("Queue: ");
int i = queue->front;
do {
printf("%d ", queue->items[i]);
i = (i + 1) % MAX_SIZE;
} while (i != (queue->rear + 1) % MAX_SIZE);
printf("\n");
}
int main() {
struct Queue queue;
initialize(&queue);
enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);
displayQueue(&queue);
int dequeued = dequeue(&queue);
printf("Dequeued element: %d\n", dequeued);
displayQueue(&queue);
return 0;
}
Question 7 (6 marks):
Write a program in C to find the shortest path in a weighted graph using Dijkstra's algorithm. Explain the algorithm and provide a sample graph for testing.
Ans. #include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 5 // Number of vertices in the graph
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == 0 && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[]) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
int sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = 0;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = 1;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main() {
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
dijkstra(graph, 0);
return 0;
}
Explanation:
- Dijkstra's algorithm finds the shortest path in a weighted graph from a source vertex to all other vertices.
- The program initializes an array
dist to store the shortest distances from the source vertex to each vertex in the graph. - It maintains a set
sptSet to keep track of vertices included in the shortest path tree. - The
minDistance function finds the vertex with the minimum distance value. - The
dijkstra function iteratively selects the minimum distance vertex, updates the distance values of its adjacent vertices, and repeats until all vertices are included in the shortest path tree. - The
printSolution function displays the shortest distances from the source vertex to all vertices.
Question 8 (6 marks):
Implement a binary search tree (BST) in C and write a function to check if it is a valid BST. Explain the logic behind your solution.
Ans. #include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int key) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
int isBSTUtil(struct Node* root, int minValue, int maxValue) {
if (root == NULL)
return 1;
if (root->data < minValue || root->data > maxValue)
return 0;
return isBSTUtil(root->left, minValue, root->data - 1) && isBSTUtil(root->right, root->data + 1, maxValue);
}
int isBST(struct Node* root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
int main() {
struct Node* root = createNode(2);
root->left = createNode(1);
root->right = createNode(3);
// Uncomment the following line to make the tree invalid
// root->right->left = createNode(1);
if (isBST(root))
printf("The tree is a valid BST.\n");
else
printf("The tree is not a valid BST.\n");
return 0;
}
Explanation:
- The program defines a structure
Node for a binary tree node. - The
createNode function creates a new node with the given key. - The
isBSTUtil function recursively checks if the tree rooted at a given node is a valid BST within a specified range (minValue and maxValue). - The
isBST function is a wrapper function that calls isBSTUtil with initial minimum and maximum values. - The main function creates a sample BST and checks whether it is a valid BST or not.
- The logic checks if the value of each node is within the permissible range for a valid BST.
