Question

Write a C function for each of the following, must be between 10 - 20 lines, include all assertions:

Binary Search Tree Insert

Binary Search Tree Remove

Binary Search Tree Traversal (Iterative version with a given stack)

Binary Heap Insert

Binary Heap Remove

Answer 1

1) INSERT

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key)

{

    /* If the tree is empty, return a new node */

    if (node == NULL) return newNode(key);

  

    /* Otherwise, recur down the tree */

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

  

    /* return the (unchanged) node pointer */

    return node;

}

2) REMOVE

/* Given a binary search tree and a key, this function deletes the key

   and returns the new root */

struct node* deleteNode(struct node* root, int key)

{

    // base case

    if (root == NULL) return root;

  

    // If the key to be deleted is smaller than the root's key,

    // then it lies in left subtree

    if (key < root->key)

        root->left = deleteNode(root->left, key);

  

    // If the key to be deleted is greater than the root's key,

    // then it lies in right subtree

    else if (key > root->key)

        root->right = deleteNode(root->right, key);

  

    // if key is same as root's key, then This is the node

    // to be deleted

    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: Get the inorder successor (smallest

        // in the right subtree)

        struct node* temp = minValueNode(root->right);

  

        // Copy the inorder successor's content to this node

        root->key = temp->key;

  

        // Delete the inorder successor

        root->right = deleteNode(root->right, temp->key);

    }

    return root;

}

3) ITERATIVE INORDER TRAVERSAL

/* Iterative function for inorder tree traversal */

void inOrder(struct Node *root)

{

  /* set current to root of binary tree */

  struct Node *current = root;

  struct sNode *s = NULL; /* Initialize stack s */

  bool done = 0;

  

  while (!done)

  {

    /* Reach the left most tNode of the current tNode */

    if(current != NULL)

    {

      /* place pointer to a tree node on the stack before traversing

        the node's left subtree */

      push(&s, current);                                               

      current = current->left;  

    }

         

    /* backtrack from the empty subtree and visit the tNode

       at the top of the stack; however, if the stack is empty,

      you are done */

    else                                                              

    {

      if (!isEmpty(s))

      {

        current = pop(&s);

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

  

        /* we have visited the node and its left subtree.

          Now, it's right subtree's turn */

        current = current->right;

      }

      else

        done = 1;

    }

  } /* end of while */  

}     

NOTE: As per Chegg policy, I am allowed to answer only 3 questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.

Answer 2

Sure, here are C functions for each of the specified operations. Please note that the provided implementations are basic and may require further refinement depending on the specific requirements of your application.

1. Binary Search Tree Insert:

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>struct TreeNode {
    int data;    struct TreeNode* left;
    struct TreeNode* right;};struct TreeNode* insert(struct TreeNode* root, int value) {    if (root == NULL) {        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        assert(newNode != NULL);
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;        return newNode;
    }    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }    return root;
}

2. Binary Search Tree Remove:

cCopy codestruct TreeNode* findMin(struct TreeNode* node) {    struct TreeNode* current = node;    while (current->left != NULL) {
        current = current->left;
    }    return current;
}struct TreeNode* removeNode(struct TreeNode* root, int value) {    if (root == NULL) {        return root;
    }    if (value < root->data) {
        root->left = removeNode(root->left, value);
    } else if (value > root->data) {
        root->right = removeNode(root->right, value);
    } else {        if (root->left == NULL) {            struct TreeNode* temp = root->right;            free(root);            return temp;
        } else if (root->right == NULL) {            struct TreeNode* temp = root->left;            free(root);            return temp;
        }        struct TreeNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = removeNode(root->right, temp->data);
    }    return root;
}

3. Binary Search Tree Traversal (Iterative version with a given stack):

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>struct TreeNode {
    int data;    struct TreeNode* left;
    struct TreeNode* right;};struct StackNode {
    struct TreeNode* node;
    struct StackNode* next;};struct Stack {
    struct StackNode* top;};struct Stack* createStack() {    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    assert(stack != NULL);    stack->top = NULL;    return stack;
}int isEmpty(struct Stack* stack) {    return stack->top == NULL;
}void push(struct Stack* stack, struct TreeNode* node) {    struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    assert(newNode != NULL);
    newNode->node = node;
    newNode->next = stack->top;    stack->top = newNode;
}struct TreeNode* pop(struct Stack* stack) {    if (isEmpty(stack)) {        return NULL;
    }    struct StackNode* temp = stack->top;    stack->top = stack->top->next;    struct TreeNode* poppedNode = temp->node;    free(temp);    return poppedNode;
}void inorderTraversal(struct TreeNode* root) {    if (root == NULL) {        return;
    }    struct Stack* stack = createStack();    struct TreeNode* current = root;    while (current != NULL || !isEmpty(stack)) {        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }

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

        current = current->right;
    }    free(stack);
}

4. Binary Heap Insert:

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>struct BinaryHeap {
    int* arr;    int capacity;    int size;
};struct BinaryHeap* createBinaryHeap(int capacity) {    struct BinaryHeap* heap = (struct BinaryHeap*)malloc(sizeof(struct BinaryHeap));
    assert(heap != NULL);
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    assert(heap->arr != NULL);
    heap->capacity = capacity;
    heap->size = 0;    return heap;
}void swap(int* a, int* b) {    int temp = *a;
    *a = *b;
    *b = temp;
}void heapifyUp(struct BinaryHeap* heap, int index) {    while (index > 0 && heap->arr[(index - 1) / 2] > heap->arr[index]) {
        swap(&heap->arr[(index - 1) / 2], &heap->arr[index]);
        index = (index - 1) / 2;
    }
}void insert(struct BinaryHeap* heap, int value) {    if (heap->size == heap->capacity) {        return;
    }

    heap->arr[heap->size] = value;
    heapifyUp(heap, heap->size);
    heap->size++;
}

5. Binary Heap Remove:

cCopy codevoid heapifyDown(struct BinaryHeap* heap, int index) {    int smallest = index;    int left = 2 * index + 1;    int right = 2 * index + 2;    if (left < heap->size && heap->arr[left] < heap->arr[smallest]) {
        smallest = left;
    }    if (right <

Answer 3

Sure, here are the C functions for each of the specified operations with assertions:

1. Binary Search Tree Insert:

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef struct TreeNode {
    int data;    struct TreeNode* left;
    struct TreeNode* right;} TreeNode;

TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;    return newNode;
}

TreeNode* insert(TreeNode* 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;
}int main() {
    TreeNode* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);

    assert(root->data == 50);
    assert(root->left->data == 30);
    assert(root->right->data == 70);
    assert(root->left->left->data == 20);
    assert(root->left->right->data == 40);    printf("Binary Search Tree Insert test passed!\n");    return 0;
}

2. Binary Search Tree Remove:

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef struct TreeNode {
    int data;    struct TreeNode* left;
    struct TreeNode* right;} TreeNode;

TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;    return newNode;
}

TreeNode* findMin(TreeNode* node) {    while (node->left != NULL) {
        node = node->left;
    }    return node;
}

TreeNode* removeNode(TreeNode* root, int value) {    if (root == NULL) {        return root;
    }    if (value < root->data) {
        root->left = removeNode(root->left, value);
    } else if (value > root->data) {
        root->right = removeNode(root->right, value);
    } else {        if (root->left == NULL) {
            TreeNode* temp = root->right;            free(root);            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;            free(root);            return temp;
        }

        TreeNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = removeNode(root->right, temp->data);
    }    return root;
}int main() {
    TreeNode* root = NULL;
    root = createNode(50);
    root->left = createNode(30);
    root->right = createNode(70);
    root->left->left = createNode(20);
    root->left->right = createNode(40);

    root = removeNode(root, 30);

    assert(root->left->data == 20);
    assert(root->left->right == NULL);    printf("Binary Search Tree Remove test passed!\n");    return 0;
}

3. Binary Search Tree Traversal (Iterative version with a given stack):

cCopy code#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef struct TreeNode {
    int data;    struct TreeNode* left;
    struct TreeNode* right;} TreeNode;typedef struct StackNode {
    TreeNode* node;    struct StackNode* next;} StackNode;

StackNode* createStackNode(TreeNode* treeNode) {
    StackNode* stackNode = (StackNode*)malloc(sizeof(StackNode));
    stackNode->node = treeNode;
    stackNode->next = NULL;    return stackNode;
}void push(StackNode** top, TreeNode* treeNode) {
    StackNode* stackNode = createStackNode(treeNode);
    stackNode->next = *top;
    *top = stackNode;
}

TreeNode* pop(StackNode** top) {    if (*top == NULL) {        return NULL;
    }
    StackNode* temp = *top;
    *top = (*top)->next;
    TreeNode* treeNode = temp->node;    free(temp);    return treeNode;
}void inorderTraversal(TreeNode* root) {
    StackNode* stack = NULL;
    TreeNode* current = root;    while (current != NULL || stack != NULL) {        while (current != NULL) {
            push(&stack, current);
            current = current->left;
        }

        current = pop(&stack);        printf("%d ", current->data);

        current = current->right;
    }
}int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = 50;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->data = 30;
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->data = 20;
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->data = 40;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->data = 70;    printf("Inorder Traversal: ");
    inorderTraversal(root);    printf("\n");

    assert(root->data == 50);
    assert(root->left->data == 30);
    assert(root->left->left->data == 20);
    assert(root->left->right->data == 40);
    assert(root->right->data == 70);    printf("Binary Search Tree Traversal test passed!\n");    return 0;
}

4. Binary Heap Insert:

cCopy code
#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef struct BinaryHeap {
    int* array;    int size;    int capacity;
} BinaryHeap;

BinaryHeap* createBinaryHeap(int capacity) {
    BinaryHeap* heap = (BinaryHeap*)malloc(sizeof(BinaryHeap));
    heap->array = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;    return heap;
}void swap(int* a, int* b) {    int temp = *a;
    *a = *b;
    *b = temp;
}void insert(BinaryHeap* heap, int value) {    if (heap->size >= heap->capacity) {        printf("Heap overflow, cannot insert.\n");        return;
    }    int currentIndex = heap->size;
    heap->array[currentIndex] = value;    while (currentIndex != 0 && heap->array[currentIndex] > heap->array[(currentIndex - 1) / 2]) {
        swap(&(heap->array[currentIndex]), &(heap->array[(currentIndex - 1) / 2]));
        currentIndex = (currentIndex - 1)