Binary Search Tree: Design and implement a C program to perform the following operations on a Binary Search Tree:
Insertion: Given a sequence of integers, insert each integer into the BST while maintaining the binary search tree property.
Deletion: Implement a function to delete a specified integer from the BST while ensuring that the resulting tree remains a valid BST.
Search: Write a function to search for a given integer in the BST and return true if it exists, false otherwise.
Traversal: Implement both depth-first (in-order, pre-order, post-order) and breadth-first traversal algorithms for the BST.
Additionally, optimize the above operations for time and space complexity where possible.
 Develop a program to work with a Heap data structure. Implement the following functionalities using Linked list:
Insertion: Design a function to insert an element into the heap while maintaining the heap property (min-heap or max-heap).
Deletion: Implement a method to remove the root element from the heap, ensuring that the heap property is preserved.
Heapify: Write a function to convert an linked list or array of elements into a heap in linear time complexity using the bottom-up heap construction approach.
Heap Sort: Utilize the heap data structure to implement the heap sort algorithm, which sorts an array of elements in ascending or descending order.