DS Questions

 

  1. Binary Search Tree (Insertion)


#include <stdio.h>

#include <conio.h>

#include <stdlib.h>


typedef struct BSTnode{

    int data;

    struct BSTnode *left,*right;

}BSTnode;


BSTnode *insert(BSTnode *T,int x){

    if(T==NULL){

        T=(BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        printf("Inserted node with value: %d\n", x);

        return(T);

    }

    if(x > T->data){

        T->right = insert(T->right,x);

        return(T);

}else{

    T->left = insert(T->left,x);

    return(T);

}

}


int main(){

    BSTnode *root = NULL;

    root = insert(root,50);

    insert(root,30);

    insert(root,20);

    insert(root,70);

    return 0;

}





  1. Binary Search Tree (Height calculation)



#include <stdio.h>

#include <stdlib.h>


typedef struct BSTnode {

    int data;

    struct BSTnode *left, *right;

} BSTnode;


BSTnode* insert(BSTnode* T, int x) {

    if (T == NULL) {

        T = (BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        return T;

    }

    if (x > T->data) {

        T->right = insert(T->right, x);

        return T;

    } else {

        T->left = insert(T->left, x);

        return T;

    }

}


int max(int a, int b) {

    return (a > b) ? a : b;

}


int getHeight(BSTnode* root) {

    if (root == NULL) {

        return -1;

    } else {

        int leftHeight = getHeight(root->left);

        int rightHeight = getHeight(root->right);

        return 1 + max(leftHeight, rightHeight);

    }

}


int main() {

    BSTnode* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 70);


    int height = getHeight(root);

    printf("Height of the BST is: %d\n", height);


    return 0;

}





  1. Binary Search Tree (Node Calculation)



#include <stdio.h>

#include <stdlib.h>


typedef struct BSTnode {

    int data;

    struct BSTnode *left, *right;

} BSTnode;


BSTnode* insert(BSTnode* T, int x) {

    if (T == NULL) {

        T = (BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        return T;

    }

    if (x > T->data) {

        T->right = insert(T->right, x);

        return T;

    } else {

        T->left = insert(T->left, x);

        return T;

    }

}


int getNodeCount(BSTnode* root) {

    if (root == NULL) {

        return 0; // Base case for an empty tree

    } else {

        return 1 + getNodeCount(root->left) + getNodeCount(root->right); // Count the current node and recursively count nodes in left and right subtrees

    }

}


int main() {

    BSTnode* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 70);


    int nodeCount = getNodeCount(root);

    printf("Number of nodes in the BST is: %d\n", nodeCount);


    return 0;

}





  1. Binary Search Tree (Pre order)


#include <stdio.h>

#include <stdlib.h>


typedef struct BSTnode {

    int data;

    struct BSTnode *left, *right;

} BSTnode;


BSTnode* insert(BSTnode* T, int x) {

    if (T == NULL) {

        T = (BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        return T;

    }

    if (x > T->data) {

        T->right = insert(T->right, x);

        return T;

    } else {

        T->left = insert(T->left, x);

        return T;

    }

}


void preorderTraversal(BSTnode* root) {

    if (root != NULL) {

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

        preorderTraversal(root->left); // Traverse the left subtree

        preorderTraversal(root->right); // Traverse the right subtree

    }

}


int main() {

    BSTnode* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 70);


    printf("Preorder traversal of the BST is: ");

    preorderTraversal(root);

    printf("\n");


    return 0;

}




  1. Binary search Tree (Inorder)


#include <stdio.h>

#include <stdlib.h>


typedef struct BSTnode {

    int data;

    struct BSTnode *left, *right;

} BSTnode;


BSTnode* insert(BSTnode* T, int x) {

    if (T == NULL) {

        T = (BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        return T;

    }

    if (x > T->data) {

        T->right = insert(T->right, x);

        return T;

    } else {

        T->left = insert(T->left, x);

        return T;

    }

}


void inorderTraversal(BSTnode* root) {

    if (root != NULL) {

        inorderTraversal(root->left); // Traverse the left subtree

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

        inorderTraversal(root->right); // Traverse the right subtree

    }

}


int main() {

    BSTnode* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 70);


    printf("Inorder traversal of the BST is: ");

    inorderTraversal(root);

    printf("\n");


    return 0;

}




  1. Binary search Tree (post order)


#include <stdio.h>

#include <stdlib.h>


typedef struct BSTnode {

    int data;

    struct BSTnode *left, *right;

} BSTnode;


BSTnode* insert(BSTnode* T, int x) {

    if (T == NULL) {

        T = (BSTnode*)malloc(sizeof(BSTnode));

        T->data = x;

        T->left = NULL;

        T->right = NULL;

        return T;

    }

    if (x > T->data) {

        T->right = insert(T->right, x);

        return T;

    } else {

        T->left = insert(T->left, x);

        return T;

    }

}


void postorderTraversal(BSTnode* root) {

    if (root != NULL) {

        postorderTraversal(root->left); // Traverse the left subtree

        postorderTraversal(root->right); // Traverse the right subtree

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

    }

}


int main() {

    BSTnode* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 70);


    printf("Postorder traversal of the BST is: ");

    postorderTraversal(root);

    printf("\n");


    return 0;

}




  1. Linked list all operation (insertion, deletion, traversing, searching)



#include <stdio.h>

#include <stdlib.h>


typedef struct Node {

    int data;

    struct Node* next;

} Node;


// Function to insert a new node at the beginning of the linked list

void insert(Node** head, int data) {

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

    newNode->data = data;

    newNode->next = *head;

    *head = newNode;

}


// Function to delete a node with a specific value from the linked list

void deleteNode(Node** head, int key) {

    Node* temp = *head;

    Node* prev = NULL;


    if (temp != NULL && temp->data == key) {

        *head = temp->next;

        free(temp);

        return;

    }


    while (temp != NULL && temp->data != key) {

        prev = temp;

        temp = temp->next;

    }


    if (temp == NULL) {

        printf("Element not found in the list\n");

        return;

    }


    prev->next = temp->next;

    free(temp);

}


// Function to print all elements of the linked list

void printList(Node* node) {

    while (node != NULL) {

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

        node = node->next;

    }

    printf("\n");

}


// Function to search for an element in the linked list

void search(Node* head, int key) {

    while (head != NULL) {

        if (head->data == key) {

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

            return;

        }

        head = head->next;

    }

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

}


int main() {

    Node* head = NULL;


    // Insert some elements

    insert(&head, 30);

    insert(&head, 20);

    insert(&head, 10);


    // Print all elements

    printf("Linked list: ");

    printList(head);


    // Search for an element

    search(head, 20);


    // Delete an element

    deleteNode(&head, 20);


    // Print all elements after deletion

    printf("Linked list after deletion: ");

    printList(head);


    return 0;

}




  1. WAP to implement stack dynamically


#include <stdio.h>

#include <stdlib.h>

struct Node {

  int data;

  struct Node* next;

};

struct Node* front = NULL;

struct Node* rear = NULL;

void enqueue(int value) {

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

  newNode->data = value;

  newNode->next = NULL;

  if (rear == NULL) {

    front = rear = newNode;

    return;

  }

  rear->next = newNode;

  rear = newNode;

}

void dequeue() {

  if (front == NULL) {

    printf("Queue is empty, cannot dequeue.\n");

    return;

  }

  struct Node* temp = front;

  front = front->next;

  if (front == NULL) {

    rear = NULL;

  }

  free(temp);

}

void display() {

  if (front == NULL) {

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

    return;

  }

  struct Node* temp = front;

  printf("Queue: ");

  while (temp != NULL) {

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

    temp = temp->next;

  }

  printf("\n");

}

int main() {

  int choice, value;

  printf("Dynamic Implementation of Queue");

  while (1) {

    printf("\n1. Enqueue\n");

    printf("2. Dequeue\n");

    printf("3. Display\n");

    printf("4. Exit\n");

    printf("Enter your choice: ");

    scanf("%d", &choice);

    switch (choice) {

      case 1:

        printf("Enter the value to be enqueued: ");

        scanf("%d", &value);

        enqueue(value);

        break;

      case 2:

        dequeue();

        break;

      case 3:

        display();

        break;

      case 4:

        exit(0);

      default:

        printf("Invalid choice\n");

    }

  }

  return 0;

}




  1. WAP to implement queue dynamically


#include <stdio.h>

#include <stdlib.h>


typedef struct Node {

    int data;

    struct Node* next;

} Node;


typedef struct Queue {

    Node *front, *rear;

} Queue;


Queue* createQueue() {

    Queue* queue = (Queue*)malloc(sizeof(Queue));

    queue->front = queue->rear = NULL;

    return queue;

}


void enqueue(Queue* queue, int data) {

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

    newNode->data = data;

    newNode->next = NULL;

    if (queue->rear == NULL) {

        queue->front = queue->rear = newNode;

        return;

    }

    queue->rear->next = newNode;

    queue->rear = newNode;

}


void dequeue(Queue* queue) {

    if (queue->front == NULL) {

        return;

    }

    Node* temp = queue->front;

    queue->front = queue->front->next;

    if (queue->front == NULL) {

        queue->rear = NULL;

    }

    free(temp);

}


void displayQueue(Queue* queue) {

    Node* current = queue->front;

    if (current == NULL) {

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

        return;

    }

    printf("Queue: ");

    while (current != NULL) {

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

        current = current->next;

    }

    printf("\n");

}


int main() {

    Queue* queue = createQueue();

    enqueue(queue, 10);

    enqueue(queue, 20);

    enqueue(queue, 30);

    displayQueue(queue);

    dequeue(queue);

    displayQueue(queue);


    return 0;

}


  1. Static stack 


Implementation of Stack using Array ( Static Implementation of Stack), include push( ), pop( ), isEmpty( ), isFull( ), size( ), display( ) method.

#include <stdio.h>

#define MAX_SIZE 10

int stack[MAX_SIZE];

int top = -1;

void push(int value) {

  if (top == MAX_SIZE - 1) {

    printf("Stack Overflow\n");

  } else {

    top++;

    stack[top] = value;

    printf("%d pushed to stack\n", value);

  }

}

void pop() {

  if (top == -1) {

    printf("Stack Underflow\n");

  } else {

    printf("%d popped from stack\n", stack[top]);

    top--;

  }

}

int isEmpty() {

  return top == -1;

}

int isFull() {

  return top == MAX_SIZE - 1;

}

int size() {

  return top + 1;

}

void display() {

  if (isEmpty()) {

    printf("Stack is empty\n");

  } else {

    printf("Stack elements are: ");

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

      printf("%d ", stack[i]);

    }

    printf("\n");

  }

}

int main() {

  int choice, value;

  printf("Static Implementation of Stack");

  while (1) {

    printf("\n1. Push\n");

    printf("2. Pop\n");

    printf("3. Display\n");

    printf("4. Size\n");

    printf("5. Is Empty\n");

    printf("6. Is Full\n");

    printf("7. Exit\n");

    printf("Enter your choice: ");

    scanf("%d", &choice);

    switch (choice) {

      case 1:

        printf("Enter the value to be pushed: ");

        scanf("%d", &value);

        push(value);

        break;

      case 2:

        pop();

        break;

      case 3:

        display();

        break;

      case 4:

        printf("Size of stack is %d\n", size());

        break;

      case 5:

        if (isEmpty()) {

          printf("Stack is empty\n");

        } else {

          printf("Stack is not empty\n");

        }

        break;

      case 6:

        if (isFull()) {

          printf("Stack is full\n");

        } else {

          printf("Stack is not full\n");

        }

        break;

      case 7:

        printf("Exiting program\n");

        return 0;

      default:

        printf("Invalid Choice\n");

    }

  }

  return 0;

}




  1. Static implementation of queue


#include <stdio.h>

#define MAX_SIZE 100


typedef struct {

    int arr[MAX_SIZE];

    int front, rear;

} Queue;


void initializeQueue(Queue *queue) {

    queue->front = -1;

    queue->rear = -1;

}


int isFull(Queue *queue) {

    return (queue->rear == MAX_SIZE - 1 && queue->front == 0) || (queue->rear + 1 == queue->front);

}


int isEmpty(Queue *queue) {

    return queue->front == -1;

}


void enqueue(Queue *queue, int item) {

    if (isFull(queue)) {

        printf("Queue is full. Cannot enqueue %d\n", item);

    } else {

        if (queue->rear == MAX_SIZE - 1 && queue->front != 0) {

            queue->rear = -1;

        }

        queue->rear++;

        queue->arr[queue->rear] = item;

        if (queue->front == -1) {

            queue->front = 0;

        }

    }

}


void dequeue(Queue *queue) {

    if (isEmpty(queue)) {

        printf("Queue is empty. Cannot dequeue\n");

    } else {

        printf("Dequeued element: %d\n", queue->arr[queue->front]);

        if (queue->front == queue->rear) {

            queue->front = queue->rear = -1;

        } else {

            if (queue->front == MAX_SIZE - 1) {

                queue->front = 0;

            } else {

                queue->front++;

            }

        }

    }

}


void display(Queue *queue) {

    if (isEmpty(queue)) {

        printf("Queue is empty\n");

    } else {

        printf("Queue elements: ");

        int i = queue->front;

        while (1) {

            printf("%d ", queue->arr[i]);

            if (i == queue->rear) {

                break;

            }

            if (i == MAX_SIZE - 1) {

                i = 0;

            } else {

                i++;

            }

        }

        printf("\n");

    }

}


int main() {

    Queue queue;

    initializeQueue(&queue);

    enqueue(&queue, 10);

    enqueue(&queue, 20);

    enqueue(&queue, 30);

    display(&queue);

    dequeue(&queue);

    display(&queue);


    return 0;

}

Comments

Post a Comment