Exercise 8: Binary Search Tree

Exercise 8:

i) Implementing a BST using Linked List.

// C Program for BST Operations like Insertion, Deletion, Search and Traversals using Linked List.

#include <stdio.h>
#include <stdlib.h>
// Structure for BST Node
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;
}
// Insert into BST
struct Node* insert(struct Node* root, int value)
{
    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);
    return root;
}
// Search operation
struct Node* search(struct Node* root, int key)
{
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}
// Find minimum node
struct Node* findMin(struct Node* root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}
// Delete operation
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 {
        // No child
        if (root->left == NULL && root->right == NULL)  
        {
            free(root);
            return NULL;
        }
        // One child (right)
        else if (root->left == NULL)
        {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        // One child (left)
        else if (root->right == NULL)
       {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        // Two children
        struct Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}
// Inorder Traversal
void inorder(struct Node* root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
// Main Function
int main()
{
    struct Node* root = NULL;
    int choice, value;
    while (1)
    {
        printf("\n----- BST MENU -----\n");
        printf("1. Insert\n");
        printf("2. Delete\n");
        printf("3. Search\n");
        printf("4. Inorder Traversal\n");
        printf("5. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);
        switch (choice)
       {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                root = insert(root, value);
                break;
            case 2:
                printf("Enter value to delete: ");
                scanf("%d", &value);
                root = deleteNode(root, value);
                break;
            case 3:
                printf("Enter value to search: ");
                scanf("%d", &value);
                if (search(root, value))
                    printf("Element Found\n");
                else
                    printf("Element Not Found\n");
                break;
            case 4:
                printf("Inorder Traversal: ");
                inorder(root);
                printf("\n");
                break;
            case 5:
                printf("Program Exited\n");
                exit(0);
            default:
                printf("Invalid Choice\n");
        }
    }
    return 0;
}

ii) Traversing of BST.

// C Program to perform inorder, preorder and postorder traversals of a BST:

#include <stdio.h>
#include <stdlib.h>
// Structure for BST Node
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};
// Create 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;
}
// Insert into BST
struct Node* insert(struct Node* root, int value)
{
    if (root == NULL)
        return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);
    return root;
}
// Inorder Traversal
void inorder(struct Node* root)
{
    if (root != NULL)
   {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
// Preorder Traversal
void preorder(struct Node* root)
{
    if (root != NULL)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
// Postorder Traversal
void postorder(struct Node* root)
{
    if (root != NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}
// Main Function
int main()
{
    struct Node* root = NULL;
    int n, value;
    printf("Enter number of nodes: ");
    scanf("%d", &n);
    printf("Enter BST elements:\n");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &value);
        root = insert(root, value);
    }
    printf("\nInorder Traversal: ");
    inorder(root);
    printf("\nPreorder Traversal: ");
    preorder(root);
    printf("\nPostorder Traversal: ");
    postorder(root);
    printf("\n");
    return 0;
}