Data Structures Lab: Assignment 1

[Link] Statement: Write a program in C to check whether a given string of braces (only) is well
formed or not.

For example, the string (((()) (())) is well formed but the song ( ) ( ) ) is all formed.

Answer:

#include <stdio.h>

#include <string.h>

#define MAX 1000

// Stack functions

int stack[MAX];

int top = -1;

void push(int val) {

if (top < MAX - 1)

stack[++top] = val;

int pop() {

if (top >= 0)

return stack[top--];

return -1; // Stack underflow (used to detect unmatched closing brace)

// Main function

int main() {

char str[MAX];

printf("Enter a string of parentheses: ");

fgets(str, sizeof(str), stdin);

int isWellFormed = 1; // Assume well-formed unless found otherwise

for (i = 0; str[i] != '\0' && str[i] != '\n'; i++) {

if (str[i] == '(') {

push('(');

} else if (str[i] == ')') {

if (pop() == -1) {

isWellFormed = 0;

break;

// If stack is not empty after processing, it's not well-formed

if (top != -1)

isWellFormed = 0;

if (isWellFormed)

printf("The string is well-formed.\n");

else

printf("The string is NOT well-formed.\n");

return 0;

Example Outputs

Input:
(((()))(()))
Output:
The string is well-formed.
Input:
()() ) (
Output:
The string is NOT well-formed.

[Link] Statement: Write a program to Searching for a specified element in a circularly linked
list.

Answer:

Approach:

1. Create a circular linked list.

2. We can do a key to search.

3. Traverse the list and compare each node’s data with the key.

4. If found, report its presence.

5. If not found after full traversal, report that the element is not present.

#include <stdio.h>

#include <stdlib.h>

// Define a node

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->next = NULL;

return newNode;

// Function to insert a node at the end of a circular linked list

struct Node* newNode = createNode(value);

if (last == NULL) {

newNode->next = newNode;

return newNode;

newNode->next = last->next;

last->next = newNode;

return newNode;

// Function to search for an element in a circular linked list

void search(struct Node* last, int key) {

if (last == NULL) {

printf("List is empty.\n");

return;

struct Node* temp = last->next;

do {

if (temp->data == key) {

printf("Element %d found in the list.\n", key);

return;

temp = temp->next;

} while (temp != last->next);

printf("Element %d not found in the list.\n", key);

}
// Main function

int main() {

struct Node* last = NULL;

int n, val, key;

printf("Enter number of nodes: ");

scanf("%d", &n);

printf("Enter %d values:\n", n);

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

scanf("%d", &val);

last = insertEnd(last, val);

printf("Enter element to search: ");

scanf("%d", &key);

search(last, key);

return 0;

Example Input/Output

Input: Enter number of nodes: 5

Enter 5 values:

10 20 30 40 50

Enter element to search: 30

Output: Element 30 found in the list.

[Link] Statement: Write a program to reverse the elements of a doubly linked list

#include <stdio.h>

#include <stdlib.h>
// Node structure

struct Node {

int data;

struct Node* prev;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = value;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

// Function to insert node at the end

void append(struct Node** headRef, int value) {

struct Node* newNode = createNode(value);

struct Node* temp = *headRef;

if (*headRef == NULL) {

*headRef = newNode;

return;

while (temp->next != NULL)

temp = temp->next;

temp->next = newNode;

newNode->prev = temp;
}

// Function to reverse the doubly linked list

void reverseList(struct Node** headRef) {

struct Node* temp = NULL;

struct Node* current = *headRef;

// Swap next and prev for all nodes

while (current != NULL) {

temp = current->prev;

current->prev = current->next;

current->next = temp;

current = current->prev; // move to "next" node (which is prev before swap)

// Adjust head

if (temp != NULL)

*headRef = temp->prev;

// Function to print the list

void printList(struct Node* head) {

while (head != NULL) {

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

head = head->next;

printf("\n");

// Main function

int main() {
 struct Node* head = NULL;

int n, val;

printf("Enter number of nodes: ");

scanf("%d", &n);

printf("Enter %d values:\n", n);

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

scanf("%d", &val);

append(&head, val);

printf("Original list: ");

printList(head);

reverseList(&head);

printf("Reversed list: ");

printList(head);

return 0;

Example Input/Output

Input:

Copy

Edit

Enter number of nodes: 5

Enter 5 values:

10 20 30 40 50

Output:
Copy

Edit

Original list: 10 20 30 40 50

Reversed list: 50 40 30 20 10

4. Program Statement: Write a program to count the leaf nodes of a tree.

Answer: Key Concepts:

• A leaf node is a node with no left or right child.

• We use recursion to traverse the tree and count nodes where both children are NULL.

#include <stdio.h>

#include <stdlib.h>

// Define the node structure

struct Node {

int data;

struct Node* left;

struct Node* right;

};

// 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;

}
// Recursive function to count leaf nodes

int countLeafNodes(struct Node* root) {

if (root == NULL)

return 0;

// If both left and right are NULL, it's a leaf node

if (root->left == NULL && root->right == NULL)

return 1;

// Otherwise, recursively count in left and right subtrees

return countLeafNodes(root->left) + countLeafNodes(root->right);

// Main function

int main() {

/*

Sample Tree:

/ \

2 3

/\ \

4 5 6

*/

struct Node* root = createNode(1);

root->left = createNode(2);

root->right = createNode(3);

root->left->left = createNode(4);

root->left->right = createNode(5);

root->right->right = createNode(6);
 int leafCount = countLeafNodes(root);

printf("Number of leaf nodes: %d\n", leafCount);

return 0;

Example Output:

javascript

CopyEdit

Number of leaf nodes: 3

(Nodes 4, 5, and 6 are leaf nodes)

[Link] Statement: Write a program to find the parent of a node if exists otherwise report
NULL.

Program Statement:

Write a program to find the parent of a given node in a binary tree.

Key Concepts:

• We perform a recursive traversal of the tree.

• At each node, check if either left or right child has the target value.

• If found, return the current node (as parent).

• If not found, recurse into subtrees.

#include <stdio.h>

#include <stdlib.h>

// Define structure for 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;

// Function to find the parent of a node

struct Node* findParent(struct Node* root, int key) {

if (root == NULL)

return NULL;

// Check if left or right child is the node we are looking for

if ((root->left != NULL && root->left->data == key) ||

(root->right != NULL && root->right->data == key)) {

return root;

// Recursively check in left and right subtrees

struct Node* leftSearch = findParent(root->left, key);

if (leftSearch != NULL)

return leftSearch;

return findParent(root->right, key);

// Main function

int main() {
/*

Sample Tree:

/ \

2 3

/\ /

4 56

*/

struct Node* root = createNode(1);

root->left = createNode(2);

root->right = createNode(3);

root->left->left = createNode(4);

root->left->right = createNode(5);

root->right->left = createNode(6);

int key;

printf("Enter the node value to find its parent: ");

scanf("%d", &key);

if (root->data == key) {

printf("The node is root. Parent: NULL\n");

} else {

struct Node* parent = findParent(root, key);

if (parent != NULL)

printf("Parent of node %d is: %d\n", key, parent->data);

else

printf("Node %d not found in the tree.\n", key);

return 0;
}

Example Input/Output

Input:

arduino

CopyEdit

Enter the node value to find its parent: 5

Output:

csharp

CopyEdit

Parent of node 5 is: 2

Input:

arduino

CopyEdit

Enter the node value to find its parent: 1

Output:

yaml

CopyEdit

The node is root. Parent: NULL

Input:

arduino

CopyEdit

Enter the node value to find its parent: 99

Output:

nginx

CopyEdit

Node 99 not found in the tree.