📚 Data Structures Problem List in C++

1. Array
2. Linked List
3. Stack
4. Queue
5. Deque (Double-Ended Queue)
6. Priority Queue
7. Hashing
8. Recursion
9. Binary Tree
10. Binary Search Tree
11. Self Balancing Binary Search Tree
12. Complete Binary Tree
13. Heap
14. Segment Tree
15. Trie(Prefix Tree)
16. Binary Indexed Tree (BIT)
17. Graph

---

1. Array

1.1 One-Dimensional Array

1. Basic Operations

1. Read and Display:
   • Write a program that reads and displays an array.
2. Sum of Elements:
   • Write a program that reads an array and displays the sum of its elements.
3. Average of Elements:
   • Write a program that reads an array and displays the average of its elements.
4. Maximum Element:
   • Write a program that reads an array and finds the maximum element.
5. Minimum Element:
   • Write a program that reads an array and finds the minimum element.

2. Insertion and Deletion

1. Insert at Specific Position:
   • Write a program that inserts a number at a specific position in an array.
2. Delete from Specific Position:
   • Write a program that deletes a number from a specific position in an array.
3. Insert at Beginning:
   • Write a program that inserts a number at the beginning of an array.
4. Insert at End:
   • Write a program that inserts a number at the end of an array.
5. Delete First Occurrence:
   • Write a program that deletes the first occurrence of a number from an array.
6. Delete All Occurrences:
   • Write a program that deletes all occurrences of a number from an array.
7. Insert in Sorted Array (Ascending):
   • Write a program that inserts a number in a sorted array, maintaining the sorted order (ascending).
8. Insert in Sorted Array (Descending):
   • Write a program that inserts a number in a sorted array, maintaining the sorted order (descending).
9. Insert Multiple Numbers in Sorted Array:
   • Write a program that inserts multiple numbers in a sorted array, maintaining the sorted order.
10. Sort and Insert:
    • Write a program that reads an unsorted array, sorts it, and then inserts a new number in the sorted array.
11. Binary Search Insertion:
    • Write a program that inserts a number in a sorted array using binary search to find the correct position.
12. Delete from Sorted Array:
    • Write a program that deletes a number from a sorted array, maintaining the sorted order.
13. Delete All Occurrences from Sorted Array:
    • Write a program that deletes all occurrences of a number from a sorted array, maintaining the sorted order.

3. Search Operations

1. Linear Search:
   • Write a program that searches for a number in an array using linear search.
2. Binary Search:
   • Write a program that searches for a number in a sorted array using binary search.

4. Sorting

1. Ascending Order:
   • Write a program that sorts an array in ascending order.
2. Descending Order:
   • Write a program that sorts an array in descending order.
3. Bubble Sort (Ascending):
   • Write a program that sorts an array using bubble sort (ascending).
4. Bubble Sort (Descending):
   • Write a program that sorts an array using bubble sort (descending).
5. Selection Sort:
   • Write a program that sorts an array using selection sort.
6. Insertion Sort:
   • Write a program that sorts an array using insertion sort.
7. Quicksort:
   • Write a program that sorts an array using quicksort.
8. Mergesort:
   • Write a program that sorts an array using mergesort.

5. Advanced Operations

1. Find Median:
   • Write a program that reads an array and displays the median.
2. Find Mode:
   • Write a program that reads an array and displays the mode (most frequent element).
3. Remove Duplicates:
   • Write a program that reads an array and removes duplicate elements.
4. Reverse Elements:
   • Write a program that reads an array and reverses the elements.
5. Right Rotation:
   • Write a program that reads an array and rotates it to the right by n positions.
6. Left Rotation:
   • Write a program that reads an array and rotates it to the left by n positions.

6. Mathematical Operations

1. Fibonacci Sequence:
   • Write a program that displays the first n Fibonacci numbers using an array.
2. Prime Numbers:
   • Write a program that displays the first n prime numbers using an array.
3. Decimal to Binary Conversion:
   • Write a program that reads any decimal number and displays the equivalent binary number.
4. Dot Product:
   • Write a program that reads two arrays and finds their dot product.
5. Intersection of Arrays:
   • Write a program that finds the intersection of two arrays.

1.2 Two-Dimensional Array

1. Basic Operations

1. Read and Display:
   • Write a program that reads and displays a 2D array (matrix).
2. Sum of Elements:
   • Write a program that reads a 2D array and finds the sum of all elements.
3. Maximum Element:
   • Write a program that reads a 2D array and finds the maximum element.
4. Transpose Matrix:
   • Write a program that reads a 2D array and transposes it.

2. Matrix Operations

1. Matrix Multiplication:
   • Write a program that multiplies two matrices.
2. Matrix Addition:
   • Write a program that adds two matrices.
3. Matrix Subtraction:
   • Write a program that subtracts two matrices.
4. Determinant:
   • Write a program that calculates the determinant of a matrix.
5. Inverse Matrix:
   • Write a program that calculates the inverse of a matrix.

3. Advanced 2D Array Operations

1. Row-wise and Column-wise Sum:
   • Write a program that performs a row-wise and column-wise sum of a matrix.
2. Saddle Point:
   • Write a program that finds the saddle point of a matrix.
3. Trace of Matrix:
   • Write a program that finds the trace of a matrix.
4. Rotate Matrix by 90 Degrees:
   • Write a program that rotates a matrix by 90 degrees.
5. Largest Square Sub-Matrix:
   • Write a program that finds the largest square sub-matrix with all 1s.

1.3 Dynamic Arrays

1. Dynamic Array Creation:
   • Write a program that implements a dynamic array (using pointers).
2. Resizing Dynamic Array:
   • Write a program that resizes a dynamic array when it gets full.

---

2. Linked List

2.1 Singly Linked List

1. Basic Operations

1. Create a Linked List and Display it:

   • Write a program to create a singly linked list and traverse and display elements of the list.

2. Insert at End:

   • Write a program to insert a node at the end of a singly linked list.

3. Insert at Beginning:

   • Write a program to insert a node at the beginning of a singly linked list.

4. Insert at Specific Position:

   • Write a program to insert a node at a specific position in a singly linked list.

5. Delete from Beginning:

   • Write a program to delete a node from the beginning of a singly linked list.

6. Delete from End:

   • Write a program to delete a node from the end of a singly linked list.

7. Delete from Specific Position:

   • Write a program to delete a node from a specific position in a singly linked list.

8. Search in Linked List:

   • Write a program to search for a specific element in a singly linked list.

9. Count Nodes:

   • Write a program to count the number of nodes in a singly linked list.

2. Advanced Operations

1. Reverse Linked List:
   • Write a program to reverse a singly linked list.
2. Detect Loop:
   • Write a program to detect if there is a loop in a singly linked list.
3. Find Middle Element:
   • Write a program to find the middle element of a singly linked list.
4. Remove Duplicates:
   • Write a program to remove duplicate nodes from a singly linked list.
5. Merge Two Linked Lists:
   • Write a program to merge two sorted singly linked lists.
6. Intersection Point of Two Linked Lists:
   • Write a program to find the intersection point of two singly linked lists.
7. Nth Node from End:
   • Write a program to find the nth node from the end of a singly linked list.

2.2 Doubly Linked List

1. Basic Operations

1. Create a Doubly Linked List:
   • Write a program to create a doubly linked list.
2. Display Doubly Linked List (Forward):
   • Write a program to traverse and display elements of a doubly linked list in the forward direction.
3. Display Doubly Linked List (Backward):
   • Write a program to traverse and display elements of a doubly linked list in the backward direction.
4. Insert at Beginning:
   • Write a program to insert a node at the beginning of a doubly linked list.
5. Insert at End:
   • Write a program to insert a node at the end of a doubly linked list.
6. Insert at Specific Position:
   • Write a program to insert a node at a specific position in a doubly linked list.
7. Delete from Beginning:
   • Write a program to delete a node from the beginning of a doubly linked list.
8. Delete from End:
   • Write a program to delete a node from the end of a doubly linked list.
9. Delete from Specific Position:
   • Write a program to delete a node from a specific position in a doubly linked list.
10. Count Nodes:
    • Write a program to count the number of nodes in a doubly linked list.

2. Advanced Operations

1. Reverse Doubly Linked List:
   • Write a program to reverse a doubly linked list.
2. Find Middle Element:
   • Write a program to find the middle element of a doubly linked list.
3. Remove Duplicates:
   • Write a program to remove duplicate nodes from a doubly linked list.

2.3 Circular Linked List

1. Basic Operations

1. Create a Circular Linked List:
   • Write a program to create a circular linked list.
2. Display Circular Linked List:
   • Write a program to traverse and display elements of a circular linked list.
3. Insert at Beginning:
   • Write a program to insert a node at the beginning of a circular linked list.
4. Insert at End:
   • Write a program to insert a node at the end of a circular linked list.
5. Delete from Beginning:
   • Write a program to delete a node from the beginning of a circular linked list.
6. Delete from End:
   • Write a program to delete a node from the end of a circular linked list.

2. Advanced Operations

1. Detect Loop in Circular Linked List:
   • Write a program to detect a loop in a circular linked list.
2. Find Length of Circular Linked List:
   • Write a program to find the length of a circular linked list.

---

3. Stack

3.1 Stack Using Array

1. Basic Operations

1. Push Operation:
   • Write a program to implement the push operation in a stack using an array.
2. Pop Operation:
   • Write a program to implement the pop operation in a stack using an array.
3. Peek Operation:
   • Write a program to implement the peek operation (view the top element) in a stack using an array.
4. Check if Empty:
   • Write a program to check if the stack is empty using an array.
5. Check if Full:
   • Write a program to check if the stack is full using an array.

2. Advanced Operations

1. Reverse a String:
   • Write a program to reverse a string using a stack implemented with an array.
2. Balanced Parentheses:
   • Write a program to check if the parentheses in an expression are balanced using a stack implemented with an array.
3. Postfix Evaluation:
   • Write a program to evaluate a postfix expression using a stack implemented with an array.
4. Infix to Postfix Conversion:
   • Write a program to convert an infix expression to postfix using a stack implemented with an array.
5. Infix to Prefix Conversion:
   • Write a program to convert an infix expression to prefix using a stack implemented with an array.

3.2 Stack Using Linked List

1. Basic Operations

1. Push Operation:
   • Write a program to implement the push operation in a stack using a linked list.
2. Pop Operation:
   • Write a program to implement the pop operation in a stack using a linked list.
3. Peek Operation:
   • Write a program to implement the peek operation (view the top element) in a stack using a linked list.
4. Check if Empty:
   • Write a program to check if the stack is empty using a linked list.

2. Advanced Operations

1. Reverse a Linked List:
   • Write a program to reverse a linked list using a stack implemented with a linked list.
2. Sort a Stack:
   • Write a program to sort a stack using a temporary stack (linked list-based stack).
3. Stack with Min Function:
   • Write a program to implement a stack with a function getMin() that retrieves the minimum element in constant time using a linked list-based stack.

3.3 Applications of Stack

1. Mathematical Applications

1. Check Palindrome:
   • Write a program to check if a string is a palindrome using a stack.
2. Next Greater Element:
   • Write a program to find the next greater element for each element in an array using a stack.
3. Sort Stack:
   • Write a program to sort a stack using another temporary stack.

2. Real-World Applications

1. Undo/Redo Functionality:
   • Write a program to implement undo and redo functionality using two stacks.
2. Stock Span Problem:
   • Write a program to solve the stock span problem using a stack.
3. Celebrity Problem:
   • Write a program to find the celebrity in a group using a stack.
4. Depth-First Search (DFS):
   • Write a program to implement DFS for graph traversal using a stack.

---

4. Queue

4.1 Queue Using Array

1. Basic Operations

1. Enqueue Operation:
   • Write a program to implement the enqueue operation in a queue using an array.
2. Dequeue Operation:
   • Write a program to implement the dequeue operation in a queue using an array.
3. Front Operation:
   • Write a program to implement the front operation (view the front element) in a queue using an array.
4. Rear Operation:
   • Write a program to implement the rear operation (view the rear element) in a queue using an array.
5. Check if Empty:
   • Write a program to check if the queue is empty using an array.
6. Check if Full:
   • Write a program to check if the queue is full using an array.

2. Advanced Operations

1. Circular Queue:
   • Write a program to implement a circular queue using an array.
2. Priority Queue:
   • Write a program to implement a priority queue using an array.
3. Double-Ended Queue (Deque):
   • Write a program to implement a deque using an array.

4.2 Queue Using Linked List

1. Basic Operations

1. Enqueue Operation:
   • Write a program to implement the enqueue operation in a queue using a linked list.
2. Dequeue Operation:
   • Write a program to implement the dequeue operation in a queue using a linked list.
3. Front Operation:
   • Write a program to implement the front operation (view the front element) in a queue using a linked list.
4. Rear Operation:
   • Write a program to implement the rear operation (view the rear element) in a queue using a linked list.
5. Check if Empty:
   • Write a program to check if the queue is empty using a linked list.

2. Advanced Operations

1. Priority Queue:
   • Write a program to implement a priority queue using a linked list.
2. Circular Queue:
   • Write a program to implement a circular queue using a linked list.
3. Deque:
   • Write a program to implement a deque using a linked list.

4.3 Applications of Queue

1. Mathematical Applications

1. Queue Reversal:
   • Write a program to reverse a queue using a stack.
2. Generate Binary Numbers:
   • Write a program to generate binary numbers from 1 to n using a queue.
3. First Non-Repeating Character:
   • Write a program to find the first non-repeating character in a stream of characters using a queue.

2. Real-World Applications

1. Task Scheduling:
   • Write a program to implement task scheduling using a queue.
2. Breadth-First Search (BFS):
   • Write a program to implement BFS for graph traversal using a queue.
3. Hot Potato Game Simulation:
   • Write a program to simulate the Hot Potato game using a queue.

---

5. Deque (Double-Ended Queue)

5.1 Array-Based Deque

1. Basic Operations

1. Insert at Front (Array-Based):
   • Write a program that inserts an element at the front of the deque (using array-based implementation).
2. Insert at Rear (Array-Based):
   • Write a program that inserts an element at the rear of the deque (using array-based implementation).
3. Delete from Front (Array-Based):
   • Write a program that deletes an element from the front of the deque (using array-based implementation).
4. Delete from Rear (Array-Based):
   • Write a program that deletes an element from the rear of the deque (using array-based implementation).
5. Peek Front (Array-Based):
   • Write a program that retrieves the front element of the deque without deleting it (using array-based implementation).
6. Peek Rear (Array-Based):
   • Write a program that retrieves the rear element of the deque without deleting it (using array-based implementation).
7. Check if Deque is Full (Array-Based):
   • Write a program that checks if the deque is full (using array-based implementation).
8. Check if Deque is Empty (Array-Based):
   • Write a program that checks if the deque is empty (using array-based implementation).

5.2 Linked List-Based Deque

1. Basic Operations

1. Insert at Front (Linked List-Based):
   • Write a program that inserts an element at the front of the deque (using linked list-based implementation).
2. Insert at Rear (Linked List-Based):
   • Write a program that inserts an element at the rear of the deque (using linked list-based implementation).
3. Delete from Front (Linked List-Based):
   • Write a program that deletes an element from the front of the deque (using linked list-based implementation).
4. Delete from Rear (Linked List-Based):
   • Write a program that deletes an element from the rear of the deque (using linked list-based implementation).
5. Peek Front (Linked List-Based):
   • Write a program that retrieves the front element of the deque without deleting it (using linked list-based implementation).
6. Peek Rear (Linked List-Based):
   • Write a program that retrieves the rear element of the deque without deleting it (using linked list-based implementation).
7. Check if Deque is Empty (Linked List-Based):
   • Write a program that checks if the deque is empty (using linked list-based implementation).

5.3 Advanced Operations

1. Circular Deque:
   • Write a program that implements a circular deque (elements wrap around the array).
2. Double-Ended Priority Queue:
   • Write a program that implements a double-ended priority queue (deque with priority).
3. Reversing a Deque:
   • Write a program that reverses the elements of a deque.
4. Deque Rotation:
   • Write a program that rotates a deque by n positions to the right.
5. Palindrome Check Using Deque:
   • Write a program that uses a deque to check if a given string is a palindrome.

---

6. Priority Queue

6.1 Array-Based Priority Queue

1. Basic Operations

1. Insert with Priority (Array-Based):
   • Write a program that inserts an element into a priority queue based on its priority (using array-based implementation).
2. Remove Highest Priority Element (Array-Based):
   • Write a program that removes the element with the highest priority from the priority queue (using array-based implementation).
3. Peek Highest Priority Element (Array-Based):
   • Write a program that retrieves the element with the highest priority without removing it from the queue (using array-based implementation).
4. Check if Priority Queue is Empty (Array-Based):
   • Write a program that checks if the priority queue is empty (using array-based implementation).

6.2 Linked List-Based Priority Queue

1. Basic Operations

1. Insert with Priority (Linked List-Based):
   • Write a program that inserts an element into a priority queue based on its priority (using linked list-based implementation).
2. Remove Highest Priority Element (Linked List-Based):
   • Write a program that removes the element with the highest priority from the priority queue (using linked list-based implementation).
3. Peek Highest Priority Element (Linked List-Based):
   • Write a program that retrieves the element with the highest priority without removing it from the queue (using linked list-based implementation).
4. Check if Priority Queue is Empty (Linked List-Based):
   • Write a program that checks if the priority queue is empty (using linked list-based implementation).

6.3 Heap-Based Priority Queue

1. Basic Operations

1. Insert with Priority (Heap-Based):
   • Write a program that inserts an element into a priority queue based on its priority (using heap-based implementation).
2. Remove Highest Priority Element (Heap-Based):
   • Write a program that removes the element with the highest priority from the priority queue (using heap-based implementation).
3. Peek Highest Priority Element (Heap-Based):
   • Write a program that retrieves the element with the highest priority without removing it from the queue (using heap-based implementation).
4. Check if Priority Queue is Empty (Heap-Based):
   • Write a program that checks if the priority queue is empty (using heap-based implementation).

6.4 Advanced Operations

1. Merge Two Priority Queues:
   • Write a program that merges two priority queues into one.
2. Change Priority of an Element:
   • Write a program that changes the priority of a specific element in the priority queue.
3. Implement Dijkstra's Algorithm:
   • Write a program that implements Dijkstra's algorithm using a priority queue.
4. Kth Largest Element in a Stream:
   • Write a program that finds the Kth largest element in a stream of integers using a priority queue.
5. Implement Huffman Coding:
   • Write a program that implements Huffman coding using a priority queue.

---

7. Hashing

7.1 Learning Hash

1. Basic Hashing with Direct Indexing:

   • Problem: Write a program to check if two strings are anagrams of each other. Two strings are called anagrams if they use the same characters in the same frequency, but in any order. For example, "listen" and "silent" are anagrams. Use an array to count the frequency of each character in both strings to determine if they are anagrams.

2. Hash Functions

   • Problem: Write a program to check if two strings are anagrams of each other. Two strings are called anagrams if they use the same characters in the same frequency, but in any order. For example, "listen" and "silent" are anagrams. Use an array to count the frequency of each character in both strings to determine if they are anagrams.
   • Use Hash Function

3. Understanding Collisions:

   • Problem: Write a program to implement basic hashing using the hash function ( h(k) = k \mod 5 ), insert the keys 5, 10, 15 into an array of size 5. Observe what happens when multiple keys hash to the same index and explain the concept of collisions.

4. Handling Collisions with Linear Probing:

   • Problem: Modify the previous program to handle collisions using linear probing. Insert the keys 5, 10, 15 into the hash table and demonstrate how collisions are resolved. Display the final hash table.

5. Handling Collisions with Quadratic Probing:

   • Problem: Write a program to handle collisions using quadratic probing with the probing sequence ( h(k, i) = (h(k) + i^2) \mod n ). Insert the keys 5, 10, 15 into a hash table of size 7 and show how quadratic probing handles collisions differently from linear probing.

6. Importance of a Good Hash Function:

   • Problem: Explain why the choice of a hash function is crucial in a hash table. Provide an example where a poor hash function leads to many collisions. Then, design a better hash function for the same set of keys and compare the results.

7. Implementing a Custom Hash Function:

   • Problem: Write a program to implement a custom hash function that distributes a given set of keys more uniformly across the hash table. Use your hash function to insert keys and display the hash table to show improved distribution.

8. Bucket Hashing Using a 2D Array:

   • Problem: Implement bucket hashing using a 2D array (array of arrays). Use the hash function ( h(k) = k \mod 3 ) and insert the keys 5, 8, 11, 14 into the hash table. Store colliding keys in the same bucket and display the contents of each bucket.

9. Hashing with Linked Lists (Chaining):

• Write a program to implement a hash table where each array index contains a linked list to handle collisions (chaining). Use a hash function to insert keys into the hash table and demonstrate how the linked lists store colliding keys.

10. Implementing Chaining to Resolve Collisions:

    • Write a program to implement chaining in a hash table to resolve collisions. Insert a set of keys into the hash table, where each collision results in a new node being added to a linked list at that index. Display the hash table with the linked lists.

11. Search Operation in a Hash Table with Chaining:

• Write a program to search for a specific key in a hash table that uses chaining. Implement the search function that traverses the linked list at the hashed index to find the key.

10. Deletion in a Hash Table with Chaining:

    • Write a program to delete a specific key from a hash table that uses chaining. Implement the deletion function that removes the key from the linked list at the hashed index.

11. Rehashing in Hash Tables:

    • Write a program to implement rehashing in a hash table when the load factor exceeds a certain threshold. Show how to rehash the existing keys into a larger hash table with a new hash function.

12. Double Hashing for Collision Resolution:

    • Write a program to implement a hash table using double hashing for collision resolution. Use two hash functions ( h_1(k) = k \mod n ) and ( h_2(k) = 1 + (k \mod (n-1)) ). Insert keys into the hash table and demonstrate how double hashing resolves collisions.

13. Implementing a Custom Hash Function:

    • Write a program to implement a custom hash function for string keys. The function should convert a string into an integer hash value that is uniformly distributed across the hash table indices.

14. Performance Analysis of Hash Tables:

    • Analyze the time complexity of various operations (insertion, search, deletion) in a hash table using different collision resolution methods (linear probing, quadratic probing, chaining). Write a report summarizing your findings.

15. Comparing Collision Resolution Strategies:

    • Write programs to implement hash tables using linear probing, quadratic probing, and chaining. Insert the same set of keys into each hash table and compare their performance in terms of collisions, search time, and load factors.

16. Implementing Open Addressing Techniques:

    • Write a program to implement a hash table using open addressing techniques (linear probing, quadratic probing, and double hashing). Demonstrate how each technique handles collisions and analyze their efficiency.

17. Designing a Hash Table for a Real-world Application:

    • Design and implement a hash table for a real-world application, such as a phonebook or dictionary. Choose an appropriate hash function and collision resolution method. Ensure efficient insertion, search, and deletion operations.

18. Implementing a Hash Map (Associative Array):

    • Write a program to implement a hash map that associates keys with values. Use a hash table with chaining to handle collisions. Implement functions to insert, search, and delete key-value pairs.

19. Handling Deletions in Open Addressing:

    • Write a program to correctly handle deletions in a hash table that uses open addressing (e.g., linear probing). Implement lazy deletion or special markers to maintain the integrity of the probing sequence.

20. Dynamic Resizing of a Hash Table:

    • Write a program to implement a hash table that dynamically resizes (expands or contracts) based on the load factor. Ensure that all elements are rehashed correctly after resizing.

21. Hashing and Load Factors:

    • Experiment with different load factors in a hash table using chaining and open addressing. Write a report on how the load factor affects the performance of the hash table operations.

7.2 Advanced Operations

1. Rehashing:
   • Write a program that resizes and rehashes a hash table when it becomes too full.
2. Find Duplicate Elements using a Hash Set:
   • Write a program that reads an array and finds all duplicate elements using a hash set.
3. Find Missing Element in a Range:
   • Write a program that finds the missing element in an array of consecutive numbers using hashing.
4. Group Anagrams:
   • Write a program that groups a list of strings into sets of anagrams using a hash table.
5. Implement LRU Cache:
   • Write a program that implements an LRU (Least Recently Used) cache using a hash map and doubly linked list.
6. Two Sum Problem:
   • Write a program that finds two numbers in an array that sum up to a target value using a hash table.
7. Check if Two Strings are Isomorphic:
   • Write a program that checks if two strings are isomorphic (can be transformed into each other by mapping characters) using a hash table.
8. Find First Non-Repeating Character:
   • Write a program that finds the first non-repeating character in a string using a hash map.
9. Longest Substring Without Repeating Characters:
   • Write a program that finds the length of the longest substring without repeating characters using hashing.
10. Count Distinct Elements in Every Window of Size K: - Write a program that counts the number of distinct elements in every window of size K in an array using a hash table.

---

8. Recursion

---

9. Binary Tree

1. Basic Binary Tree Creation:

   • Problem: Write a program to create a basic binary tree with nodes containing the values 10, 20, 30, 40, 50. Display the structure of the tree.

2. Inorder, Preorder, and Postorder Traversal:

   • Problem: Write a program to implement the inorder, preorder, and postorder traversal algorithms for a binary tree. Use the tree created in the previous problem and print the results of each traversal.

3. Insert a Node in a Binary Tree:

   • Problem: Write a program to insert a node into a binary tree at the first available position (level order insertion). Insert the value 60 into the binary tree created in the first problem.

4. Find the Height of a Binary Tree:

   • Problem: Write a function to calculate the height of a binary tree. Use the tree from the previous problems and determine its height.

5. Level Order Traversal:

   • Problem: Write a program to implement level order traversal of a binary tree using a queue. Print the nodes level by level.

6. Find the Maximum Element in a Binary Tree:

   • Problem: Write a function to find the maximum element in a binary tree. Use recursion to compare the values of nodes and find the maximum.

7. Count the Number of Nodes in a Binary Tree:

   • Problem: Write a function to count the total number of nodes in a binary tree. Use the tree from the previous problems and print the result.

8. Count Leaf Nodes in a Binary Tree:

   • Problem: Write a function to count the number of leaf nodes (nodes with no children) in a binary tree. Test this function using the tree created previously.

9. Check if Two Trees are Identical:

   • Problem: Write a function to check if two binary trees are identical in terms of structure and node values. Create two identical trees and one different tree to test your function.

10. Find the Depth of a Specific Node:

    • Problem: Write a function to find the depth (distance from the root) of a specific node in a binary tree. Use the tree created in the previous problems and find the depth of node 40.

11. Mirror a Binary Tree:

    • Problem: Write a function to convert a binary tree into its mirror image. Apply this function to the tree from earlier problems and display the mirrored structure.

12. Check if a Binary Tree is Balanced:

    • Problem: Write a function to check if a binary tree is balanced. A balanced tree is one in which the height difference between the left and right subtrees of any node is at most 1.

13. Find the Lowest Common Ancestor (LCA):

    • Problem: Write a function to find the lowest common ancestor (LCA) of two nodes in a binary tree. Use the tree from previous problems to find the LCA of nodes 20 and 40.

14. Print All Paths from Root to Leaf:

    • Problem: Write a program to print all the paths from the root node to the leaf nodes of a binary tree. Use the tree from earlier problems to list all such paths.

15. Check if a Binary Tree is Symmetric:

    • Problem: Write a function to check if a binary tree is symmetric around its center (i.e., it is a mirror of itself). Test your function with both symmetric and asymmetric trees.

16. Convert a Binary Tree to a Doubly Linked List:

    • Problem: Write a function to convert a binary tree into a doubly linked list using in-order traversal. Display the resulting doubly linked list.

17. Find the Diameter of a Binary Tree:

    • Problem: Write a function to determine the diameter of a binary tree (the longest path between two leaf nodes). Use the tree from earlier problems and calculate its diameter.

18. Print Nodes at K Distance from the Root:

    • Problem: Write a function to print all nodes at a distance k from the root of a binary tree. Use the tree created earlier and print nodes at distance 2.

19. Zigzag (Spiral) Level Order Traversal:

    • Problem: Write a program to perform a zigzag level order traversal of a binary tree. Alternate the traversal direction for each level of the tree.

20. Convert a Binary Tree to its Sum Tree:

    • Problem: Write a function to convert a binary tree into its sum tree, where each node contains the sum of the values of its left and right subtrees. Use the original tree and display the new tree structure.

21. Check if a Binary Tree is a Subtree of Another Tree:

    • Problem: Write a function to check if a given binary tree is a subtree of another binary tree. Create a main tree and a subtree to test this function.

22. Boundary Traversal of a Binary Tree:

    • Problem: Write a program to perform the boundary traversal of a binary tree. Print the boundary nodes in anti-clockwise direction starting from the root.

23. Serialize and Deserialize a Binary Tree:

    • Problem: Write a function to serialize a binary tree (convert it into a string) and another function to deserialize the string back into the original binary tree. Test both functions to ensure they are working correctly.

24. Find All Nodes at Distance K from a Given Node:

    • Problem: Write a function to find all nodes that are at distance k from a given node in a binary tree. Use the tree from earlier problems and find nodes at distance 2 from node 20.

25. Flatten a Binary Tree to a Linked List:

    • Problem: Write a function to flatten a binary tree to a linked list in-place following preorder traversal. Use the tree from earlier problems and display the linked list.

---

10. Binary Search Tree

1. Basic Binary Search Tree Creation:

   • Problem: Write a program to create a binary search tree with the following values: 50, 30, 20, 40, 70, 60, 80. Display the structure of the tree.

2. Insert a Node in a Binary Search Tree:

   • Problem: Insert the value 65 into the binary search tree created in the previous problem.

3. Search for a Node in a Binary Search Tree:

   • Problem: Write a function to search for a node with a specific value in a binary search tree. Use the tree created in the first problem to search for the value 40.

4. Find the Minimum and Maximum in a Binary Search Tree:

   • Problem: Write functions to find the minimum and maximum values in a binary search tree. Use the BST from the previous problems to find both.

5. Delete a Node from a Binary Search Tree:

   • Problem: Write a function to delete a node from a binary search tree. Use the tree from the previous problem and delete the node with the value 70.

6. Find the Height of a Binary Search Tree:

   • Problem: Write a function to find the height of a binary search tree. Use the BST created earlier and determine its height.

7. Inorder Successor in a Binary Search Tree:

   • Problem: Write a function to find the inorder successor of a given node in a binary search tree. Use the tree created earlier and find the inorder successor of node 60.

8. Check if a Tree is a Binary Search Tree:

   • Problem: Write a function to check if a given binary tree is a binary search tree. Create a sample tree and test this function.

9. Find the Lowest Common Ancestor (LCA) in a Binary Search Tree:

   • Problem: Write a function to find the lowest common ancestor of two nodes in a binary search tree. Use the tree from earlier problems to find the LCA of nodes 20 and 40.

10. Find the Kth Smallest Element in a Binary Search Tree:

    • Problem: Write a function to find the k-th smallest element in a binary search tree. Use the tree created earlier and find the 3rd smallest element.

11. Check if a Binary Search Tree is Balanced:

    • Problem: Write a function to check if a binary search tree is balanced. A balanced tree is one where the height difference between left and right subtrees is at most 1. Use the tree from the previous problems.

12. Convert a Binary Search Tree to a Doubly Linked List:

    • Problem: Write a function to convert a binary search tree into a doubly linked list using in-order traversal. Display the resulting linked list.

13. Find the Closest Value to a Given Target in a Binary Search Tree:

    • Problem: Write a function to find the value in a binary search tree that is closest to a given target value. Use the tree created earlier and find the closest value to 55.

14. Find the Mode (Most Frequent Element) in a Binary Search Tree:

    • Problem: Write a function to find the mode (the value that appears most frequently) in a binary search tree. Create a BST with duplicate values and find the mode.

15. Inorder Predecessor in a Binary Search Tree:

    • Problem: Write a function to find the inorder predecessor of a given node in a binary search tree. Use the tree created earlier and find the inorder predecessor of node 40.

16. Merge Two Binary Search Trees:

    • Problem: Write a program to merge two binary search trees into one binary search tree. Create two sample BSTs and merge them.

17. Print All Elements in a Given Range in a Binary Search Tree:

    • Problem: Write a function to print all elements in a binary search tree that lie within a given range [low, high]. Use the tree created earlier to print elements within the range [30, 70].

18. Find the Floor and Ceiling of a Value in a Binary Search Tree:

    • Problem: Write a function to find the floor (largest value smaller than or equal to the target) and ceiling (smallest value larger than or equal to the target) of a given value in a binary search tree. Use the tree created earlier to find the floor and ceiling of 65.

19. Check if Two Binary Search Trees are Identical:

    • Problem: Write a function to check if two binary search trees are identical in terms of structure and node values. Create two identical trees and one different tree to test your function.

20. Convert a Sorted Array to a Binary Search Tree:

    • Problem: Write a function to convert a sorted array into a balanced binary search tree. Use the sorted array [10, 20, 30, 40, 50, 60, 70, 80] and create a balanced BST.

21. Find the Diameter of a Binary Search Tree:

    • Problem: Write a function to calculate the diameter (the longest path between two leaf nodes) of a binary search tree. Use the tree from earlier problems and calculate its diameter.

22. Find All Nodes at a Given Distance from a Node in a Binary Search Tree:

    • Problem: Write a function to find all nodes that are at a distance k from a given node in a binary search tree. Use the tree created earlier and find nodes at distance 2 from node 30.

23. Print Nodes at K Distance from the Root in a Binary Search Tree:

    • Problem: Write a function to print all nodes at a distance k from the root of a binary search tree. Use the tree created earlier and print nodes at distance 2.

24. Serialize and Deserialize a Binary Search Tree:

    • Problem: Write functions to serialize a binary search tree (convert it into a string) and deserialize the string back into the original tree. Test both functions to ensure they are working correctly.

25. Build a BST to hold only unique elements (Set):

    • Problem: Write a program to create Binary Search Tree(BST) to hold unique elements like Set.

---

11. Self Balancing Binary Search Tree

1. Create an AVL Tree:

   • Problem: Write a program to create an AVL tree by inserting the following values: 30, 20, 40, 10, 25, 35, 50. Ensure that the tree remains balanced after each insertion and display the final tree.

2. Insert a Node in an AVL Tree:

   • Problem: Write a function to insert a node into an AVL tree. Insert the value 15 into the AVL tree created in the previous problem, and ensure that the tree remains balanced.

3. Delete a Node from an AVL Tree:

   • Problem: Write a function to delete a node from an AVL tree while maintaining the tree's balance. Use the AVL tree from the previous problems and delete the node with the value 40.

4. Check the Balance Factor of Nodes in an AVL Tree:

   • Problem: Write a function to calculate and print the balance factor (difference between the heights of left and right subtrees) of every node in an AVL tree. Use the AVL tree created earlier.

5. Right and Left Rotations in an AVL Tree:

   • Problem: Write functions to perform right and left rotations on nodes in an AVL tree. Use these functions to rotate the AVL tree created earlier at the root node.

6. Rebalance an AVL Tree:

   • Problem: Write a function to rebalance an AVL tree after an insertion or deletion. Test this function by inserting 45 and deleting 10 from the AVL tree created earlier.

7. Create a Red-Black Tree:

   • Problem: Write a program to create a Red-Black Tree by inserting the following values: 50, 30, 70, 20, 40, 60, 80. Ensure that the Red-Black properties (coloring, balancing, etc.) are maintained after every insertion.

8. Insert a Node in a Red-Black Tree:

   • Problem: Write a function to insert a node into a Red-Black Tree while maintaining the Red-Black Tree properties. Insert the value 90 into the Red-Black Tree created in the previous problem.

9. Delete a Node from a Red-Black Tree:

   • Problem: Write a function to delete a node from a Red-Black Tree while maintaining its properties. Use the Red-Black Tree from the previous problems and delete the node with the value 30.

10. Check Red-Black Tree Properties:

    • Problem: Write a function to verify that a tree satisfies all Red-Black Tree properties (every node is either red or black, the root is black, red nodes have black children, etc.). Test this function with the Red-Black Tree created earlier.

11. Right and Left Rotations in a Red-Black Tree:

    • Problem: Write functions to perform right and left rotations on nodes in a Red-Black Tree. Use these functions to rotate the Red-Black Tree created earlier at the root node.

12. Rebalance a Red-Black Tree:

    • Problem: Write a function to rebalance a Red-Black Tree after an insertion or deletion. Test this function by inserting 65 and deleting 50 from the Red-Black Tree created earlier.

13. Find the Height of an AVL/Red-Black Tree:

    • Problem: Write a function to calculate the height of an AVL tree and a Red-Black tree. Compare the heights of both trees created earlier.

14. Find the Minimum and Maximum in an AVL/Red-Black Tree:

    • Problem: Write functions to find the minimum and maximum values in both an AVL tree and a Red-Black Tree. Use the trees created earlier to find both values.

15. Find the Kth Smallest Element in an AVL/Red-Black Tree:

    • Problem: Write a function to find the k-th smallest element in both an AVL tree and a Red-Black Tree. Use the trees created earlier and find the 3rd smallest element in each.

16. Find the Lowest Common Ancestor (LCA) in an AVL/Red-Black Tree:

    • Problem: Write a function to find the lowest common ancestor of two nodes in an AVL tree and a Red-Black Tree. Use the trees created earlier to find the LCA of nodes 20 and 40.

17. Find the Inorder Successor and Predecessor in an AVL/Red-Black Tree:

    • Problem: Write functions to find the inorder successor and inorder predecessor of a given node in both an AVL tree and a Red-Black Tree. Use the trees created earlier to find the inorder successor and predecessor of node 40.

18. Check if Two AVL/Red-Black Trees are Identical:

    • Problem: Write a function to check if two AVL trees or two Red-Black Trees are identical in terms of structure and node values. Create two identical trees and one different tree to test your function.

19. Convert a Sorted Array to an AVL/Red-Black Tree:

    • Problem: Write a function to convert a sorted array into an AVL tree and a Red-Black Tree. Use the sorted array [10, 20, 30, 40, 50, 60, 70, 80] to create both trees.

20. Print All Elements in a Given Range in an AVL/Red-Black Tree:

    • Problem: Write a function to print all elements in both an AVL tree and a Red-Black Tree that lie within a given range [low, high]. Use the trees created earlier to print elements within the range [30, 70].

21. Find the Floor and Ceiling of a Value in an AVL/Red-Black Tree:

    • Problem: Write a function to find the floor (largest value smaller than or equal to the target) and ceiling (smallest value larger than or equal to the target) of a given value in both an AVL tree and a Red-Black Tree. Use the trees created earlier to find the floor and ceiling of 65.

22. Print Nodes at K Distance from the Root in an AVL/Red-Black Tree:

    • Problem: Write a function to print all nodes at a distance k from the root in both an AVL tree and a Red-Black Tree. Use the trees created earlier and print nodes at distance 2.

23. Serialize and Deserialize an AVL/Red-Black Tree:

    • Problem: Write functions to serialize an AVL tree and a Red-Black Tree (convert them into a string) and deserialize the string back into the original trees. Test both functions to ensure they are working correctly.

24. Find the Diameter of an AVL/Red-Black Tree:

    • Problem: Write a function to calculate the diameter (the longest path between two leaf nodes) of both an AVL tree and a Red-Black Tree. Use the trees from earlier problems and calculate their diameters.

25. Check if an AVL/Red-Black Tree is Balanced:

    • Problem: Write a function to check if a given AVL tree or Red-Black Tree is balanced. The AVL tree should satisfy the balance factor property, and the Red-Black Tree should satisfy its balancing rules. Use the trees created earlier to test this function.

---

12. Complete Binary Tree

1. Basic Complete Binary Tree Creation:

   • Problem: Write a program to create a complete binary tree with the following values: 10, 20, 30, 40, 50, 60, 70. Display the structure of the complete binary tree.

2. Insert a Node in a Complete Binary Tree:

   • Problem: Write a function to insert a new node in a complete binary tree at the first available position (level order insertion). Insert the value 80 into the complete binary tree created in the previous problem.

3. Level Order Traversal of a Complete Binary Tree:

   • Problem: Write a program to perform level order traversal of a complete binary tree. Use a queue to traverse and print the nodes level by level.

4. Find the Height of a Complete Binary Tree:

   • Problem: Write a function to calculate the height of a complete binary tree. Use the tree created in the previous problems and determine its height.

5. Find the Number of Nodes in a Complete Binary Tree:

   • Problem: Write a function to count the total number of nodes in a complete binary tree. Use the tree from the previous problems and print the result.

6. Check if a Tree is Complete:

   • Problem: Write a function to check if a given binary tree is a complete binary tree. Test this function with both complete and incomplete trees.

7. Find the Last Node in a Complete Binary Tree:

   • Problem: Write a function to find the last node in a complete binary tree (the rightmost node at the deepest level). Use the tree created earlier to find the last node.

8. Delete the Last Node in a Complete Binary Tree:

   • Problem: Write a function to delete the last node in a complete binary tree. Delete the last node from the tree created in the previous problem.

9. Inorder Traversal of a Complete Binary Tree:

   • Problem: Write a program to perform inorder traversal of a complete binary tree. Use the tree created earlier and print the nodes in inorder.

10. Preorder Traversal of a Complete Binary Tree:

    • Problem: Write a program to perform preorder traversal of a complete binary tree. Use the tree created earlier and print the nodes in preorder.

11. Postorder Traversal of a Complete Binary Tree:

    • Problem: Write a program to perform postorder traversal of a complete binary tree. Use the tree created earlier and print the nodes in postorder.

12. Check if a Complete Binary Tree is a Full Binary Tree:

    • Problem: Write a function to check if a complete binary tree is also a full binary tree. A full binary tree is a tree where every node has either 0 or 2 children.

13. Find the Depth of a Complete Binary Tree:

    • Problem: Write a function to calculate the depth of a complete binary tree. Use the tree created earlier to find its depth.

14. Print Nodes at K Distance from the Root in a Complete Binary Tree:

    • Problem: Write a function to print all nodes at a distance k from the root of a complete binary tree. Use the tree created earlier and print nodes at distance 2.

15. Find the Maximum Element in a Complete Binary Tree:

    • Problem: Write a function to find the maximum element in a complete binary tree. Use the tree from the previous problems and determine the maximum element.

16. Find the Minimum Element in a Complete Binary Tree:

    • Problem: Write a function to find the minimum element in a complete binary tree. Use the tree from the previous problems and determine the minimum element.

17. Find the Leaf Nodes in a Complete Binary Tree:

    • Problem: Write a function to find and print all the leaf nodes in a complete binary tree. Use the tree created earlier to find its leaf nodes.

18. Find the Diameter of a Complete Binary Tree:

    • Problem: Write a function to determine the diameter of a complete binary tree (the longest path between two leaf nodes). Use the tree from the previous problems and calculate its diameter.

19. Print All Paths from Root to Leaf in a Complete Binary Tree:

    • Problem: Write a function to print all the paths from the root node to each leaf node in a complete binary tree. Use the tree created earlier to list all such paths.

20. Check if Two Complete Binary Trees are Identical:

    • Problem: Write a function to check if two complete binary trees are identical in terms of structure and node values. Create two identical trees and one different tree to test your function.

21. Serialize and Deserialize a Complete Binary Tree:

    • Problem: Write functions to serialize a complete binary tree (convert it into a string) and deserialize the string back into the original tree. Test both functions to ensure they are working correctly.

22. Convert a Complete Binary Tree to a Doubly Linked List:

    • Problem: Write a function to convert a complete binary tree into a doubly linked list using level order traversal. Display the resulting doubly linked list.

23. Flatten a Complete Binary Tree to a Linked List:

    • Problem: Write a function to flatten a complete binary tree into a linked list in-place following level order traversal. Use the tree from the previous problems and display the linked list.

24. Check if a Complete Binary Tree is a Perfect Binary Tree:

    • Problem: Write a function to check if a complete binary tree is also a perfect binary tree. A perfect binary tree is one where all levels are completely filled.

25. Find the Lowest Common Ancestor (LCA) in a Complete Binary Tree:

    • Problem: Write a function to find the lowest common ancestor (LCA) of two nodes in a complete binary tree. Use the tree created earlier to find the LCA of two nodes.

---

13. Heap

Max-Heap Problems:

1. Basic Max-Heap Creation:

   • Problem: Write a program to create a max-heap from the following values: 10, 20, 30, 40, 50, 60, 70. Display the structure of the heap.

2. Insert a Node into a Max-Heap:

   • Problem: Write a function to insert a new node into a max-heap. Insert the value 80 into the max-heap created earlier and ensure that the heap property is maintained.

3. Delete the Maximum Element from a Max-Heap:

   • Problem: Write a function to delete the maximum element (the root) from a max-heap. Delete the root from the max-heap created earlier and maintain the heap property.

4. Heapify an Array into a Max-Heap:

   • Problem: Write a function to convert an unsorted array into a max-heap using the heapify process. Use the array [5, 15, 10, 20, 25, 30, 35] to create the max-heap.

5. Find the Maximum Element in a Max-Heap:

   • Problem: Write a function to find and return the maximum element in a max-heap. Use the heap created earlier to find the maximum element.

6. Extract the Maximum Element from a Max-Heap:

   • Problem: Write a function to extract (remove and return) the maximum element from a max-heap. Ensure that the heap property is maintained after the extraction.

7. Find the Kth Smallest Element using a Max-Heap:

   • Problem: Write a function to find the k-th smallest element in an array using a max-heap. Use the array [5, 15, 10, 20, 25, 30, 35] and find the 2nd smallest element.

8. Check if a Given Array Represents a Max-Heap:

   • Problem: Write a function to check if a given array represents a valid max-heap. Use the array [70, 50, 60, 40, 30, 10, 20] and check if it represents a valid max-heap.

9. Merge Two Max-Heaps:

   • Problem: Write a function to merge two max-heaps into a single max-heap. Use the max-heaps [50, 20, 30] and [70, 10, 40] and merge them into one max-heap.

10. Convert a Max-Heap to a Min-Heap:

    • Problem: Write a function to convert a max-heap into a min-heap. Use the max-heap created earlier and convert it to a min-heap.

11. Implement Heapsort using a Max-Heap:

    • Problem: Write a program to implement the heapsort algorithm using a max-heap. Use the array [10, 20, 30, 40, 50, 60, 70] and sort it in descending order using heapsort.

12. Find the Height of a Max-Heap:

    • Problem: Write a function to calculate the height of a max-heap. Use the max-heap created earlier and determine its height.

---

Min-Heap Problems:

1. Basic Min-Heap Creation:

• Problem: Write a program to create a min-heap from the following values: 10, 20, 30, 40, 50, 60, 70. Display the structure of the heap.

2. Insert a Node into a Min-Heap:

• Problem: Write a function to insert a new node into a min-heap. Insert the value 5 into the min-heap created earlier and ensure that the heap property is maintained.

3. Delete the Minimum Element from a Min-Heap:

• Problem: Write a function to delete the minimum element (the root) from a min-heap. Delete the root from the min-heap created earlier and maintain the heap property.

4. Heapify an Array into a Min-Heap:

• Problem: Write a function to convert an unsorted array into a min-heap using the heapify process. Use the array [50, 10, 20, 60, 30, 15] to create the min-heap.

5. Find the Minimum Element in a Min-Heap:

• Problem: Write a function to find and return the minimum element in a min-heap. Use the heap created earlier to find the minimum element.

6. Extract the Minimum Element from a Min-Heap:

• Problem: Write a function to extract (remove and return) the minimum element from a min-heap. Ensure that the heap property is maintained after the extraction.

7. Find the Kth Largest Element using a Min-Heap:

• Problem: Write a function to find the k-th largest element in an array using a min-heap. Use the array [50, 20, 30, 60, 70, 10] and find the 3rd largest element.

8. Check if a Given Array Represents a Min-Heap:

• Problem: Write a function to check if a given array represents a valid min-heap. Use the array [10, 15, 20, 40, 50, 60, 70] and check if it represents a valid min-heap.

9. Merge Two Min-Heaps:

• Problem: Write a function to merge two min-heaps into a single min-heap. Use the min-heaps [10, 30, 50] and [5, 20, 60] and merge them into one min-heap.

10. Convert a Min-Heap to a Max-Heap:

    • Problem: Write a function to convert a min-heap into a max-heap. Use the min-heap created earlier and convert it to a max-heap.

11. Implement Heapsort using a Min-Heap:

    • Problem: Write a program to implement the heapsort algorithm using a min-heap. Use the array [70, 50, 60, 40, 30, 20, 10] and sort it in ascending order using heapsort.

12. Find the Height of a Min-Heap:

    • Problem: Write a function to calculate the height of a min-heap. Use the min-heap created earlier and determine its height.

---

Additional Heap Problems:

1. Print All Elements in a Given Range in a Min-Heap:

   • Problem: Write a function to print all elements in a min-heap that lie within a given range [low, high]. Use the min-heap created earlier and print elements within the range [10, 40].

2. Insert Multiple Elements into a Heap:

   • Problem: Write a function to insert multiple elements into a max-heap or a min-heap. Insert the values [35, 25, 15] into the heap created earlier and maintain the heap property.

3. Find the LCA (Lowest Common Ancestor) of Two Nodes in a Binary Heap:

   • Problem: Write a function to find the lowest common ancestor (LCA) of two nodes in a binary heap. Use the heap created earlier to find the LCA of nodes 50 and 70.

4. Implement Heapsort for Ascending Order using a Min-Heap:

   • Problem: Write a program to implement the heapsort algorithm to sort an array in ascending order using a min-heap. Use the array [70, 50, 60, 40, 30, 20, 10] and sort it in ascending order using the heapsort algorithm.
   • Approach: The min-heap guarantees that the minimum element is always at the root. You can repeatedly extract the minimum element from the min-heap and store it in the sorted array to achieve ascending order.

5. Implement Heapsort for Descending Order using a Max-Heap:

   • Problem: Write a program to implement the heapsort algorithm to sort an array in descending order using a max-heap. Use the array [10, 20, 30, 40, 50, 60, 70] and sort it in descending order using the heapsort algorithm.
   • Approach: The max-heap guarantees that the maximum element is always at the root. You can repeatedly extract the maximum element from the max-heap and store it in the sorted array to achieve descending order.

---

14. Segment Tree

1. Basic Segment Tree Creation:

   • Problem: Write a program to create a segment tree for the following array: [1, 3, 5, 7, 9, 11]. Each node of the tree should store the sum of a range of elements from the array.

2. Range Sum Query in a Segment Tree:

   • Problem: Write a function to find the sum of elements within a given range in a segment tree. Use the segment tree created in the previous problem and find the sum of elements between index 1 and 4.

3. Update an Element in a Segment Tree:

   • Problem: Write a function to update an element in the segment tree. Change the value at index 3 to 6 in the array [1, 3, 5, 7, 9, 11] and update the segment tree accordingly.

4. Range Minimum Query (RMQ) in a Segment Tree:

   • Problem: Write a function to find the minimum element in a given range using a segment tree. Use the segment tree created earlier and find the minimum element between index 1 and 4.

5. Range Maximum Query (RMQ) in a Segment Tree:

   • Problem: Write a function to find the maximum element in a given range using a segment tree. Use the segment tree created earlier and find the maximum element between index 1 and 4.

6. Range GCD Query in a Segment Tree:

   • Problem: Write a function to find the GCD (Greatest Common Divisor) of elements within a given range in a segment tree. Use the array [2, 4, 6, 8, 16] and find the GCD of the elements between index 1 and 3.

7. Range Product Query in a Segment Tree:

   • Problem: Write a function to calculate the product of elements in a given range using a segment tree. Use the array [1, 2, 3, 4, 5, 6] and find the product of elements between index 2 and 5.

8. Lazy Propagation for Range Updates in a Segment Tree:

   • Problem: Write a function to implement lazy propagation for range updates in a segment tree. Update the range [2, 4] by adding 3 to each element in the array [1, 3, 5, 7, 9, 11] and update the segment tree accordingly.

9. Range Sum with Lazy Propagation in a Segment Tree:

   • Problem: Write a function to find the sum of elements in a given range using lazy propagation in a segment tree. Use the segment tree from the previous problem and find the sum of elements between index 1 and 5.

10. Point Update in a Segment Tree:

    • Problem: Write a function to perform a point update (change a single element) in a segment tree. Change the value at index 2 to 10 in the array [1, 3, 5, 7, 9, 11] and update the segment tree accordingly.

11. Range XOR Query in a Segment Tree:

    • Problem: Write a function to find the XOR of elements in a given range using a segment tree. Use the array [1, 2, 3, 4, 5, 6] and find the XOR of elements between index 1 and 4.

12. Range Sum with Point Update in a Segment Tree:

    • Problem: Write a function to calculate the sum of elements within a given range and update a specific element in a segment tree. Use the array [1, 3, 5, 7, 9, 11], find the sum of elements between index 1 and 4, and update the value at index 3 to 6.

13. Find the Kth Smallest Element using a Segment Tree:

    • Problem: Write a function to find the k-th smallest element in a given range using a segment tree. Use the array [5, 3, 9, 1, 7, 4] and find the 3rd smallest element in the range [1, 5].

14. Range Median Query in a Segment Tree:

    • Problem: Write a function to find the median of elements within a given range using a segment tree. Use the array [1, 5, 9, 7, 3, 11] and find the median of elements between index 1 and 4.

15. Range Maximum with Point Update in a Segment Tree:

    • Problem: Write a function to calculate the maximum element in a given range and update a specific element in a segment tree. Use the array [1, 3, 5, 7, 9, 11], find the maximum element between index 0 and 3, and update the value at index 2 to 10.

16. Build a Segment Tree from a Given Array:

    • Problem: Write a program to construct a segment tree from a given array [8, 4, 2, 6, 3, 7]. Each node of the tree should store the sum of a range of elements from the array.

17. Range Sum and Range Update with Lazy Propagation:

    • Problem: Write a function to find the sum of elements in a given range and perform a range update using lazy propagation in a segment tree. Use the array [1, 3, 5, 7, 9, 11], update the range [1, 3] by adding 5 to each element, and find the sum of elements between index 1 and 5.

18. Range Sum of Even Numbers in a Segment Tree:

    • Problem: Write a function to find the sum of even numbers in a given range using a segment tree. Use the array [2, 4, 6, 8, 10, 12] and find the sum of even numbers between index 1 and 4.

19. Range Sum of Odd Numbers in a Segment Tree:

    • Problem: Write a function to find the sum of odd numbers in a given range using a segment tree. Use the array [1, 3, 5, 7, 9, 11] and find the sum of odd numbers between index 0 and 5.

20. Range Sum of Primes in a Segment Tree:

    • Problem: Write a function to find the sum of prime numbers in a given range using a segment tree. Use the array [2, 3, 4, 5, 6, 7, 8] and find the sum of prime numbers between index 1 and 6.

21. Check if a Given Element Exists in a Segment Tree:

    • Problem: Write a function to check if a given element exists within a specific range in a segment tree. Use the array [10, 20, 30, 40, 50, 60] and check if the element 30 exists between index 1 and 4.

22. Range Modulo Query in a Segment Tree:

    • Problem: Write a function to find the modulo m of the sum of elements within a given range in a segment tree. Use the array [1, 2, 3, 4, 5, 6], find the sum of elements between index 2 and 5, and return the result modulo 3.

23. Find the Range with Maximum Sum in a Segment Tree:

    • Problem: Write a function to find the range with the maximum sum in a segment tree. Use the array [3, -2, 5, -1, 2, 6, -3] and find the range with the maximum sum.

24. Find the Number of Elements Greater Than a Given Value in a Range:

    • Problem: Write a function to count the number of elements greater than a given value x in a specific range using a segment tree. Use the array [10, 20, 30, 40, 50, 60] and find how many elements are greater than 25 between index 1 and 5.

25. Find the Number of Elements Less Than a Given Value in a Range:

    • Problem: Write a function to count the number of elements less than a given value x in a specific range using a segment tree. Use the array [10, 20, 30, 40, 50, 60] and find how many elements are less than 35 between index 0 and 4.

---

15. Trie(Prefix Tree)

1. Basic Trie Insertion:

   • Problem: Write a program to implement a basic Trie. Insert the following words: ["apple", "app", "bat", "ball", "cat"] into the Trie and display the structure of the Trie.

2. Search for a Word in a Trie:

   • Problem: Write a function to search for a word in a Trie. Use the Trie created earlier and search for the words "apple", "bat", and "dog".

3. Prefix Search in a Trie:

   • Problem: Write a function to search for all words that start with a given prefix. Use the Trie created earlier to find words that start with the prefix "ap" and "ba".

4. Check if a Word Exists in a Trie:

   • Problem: Write a function to check if a specific word exists in the Trie. Use the Trie from previous problems and check for the existence of "cat", "bat", and "cap".

5. Delete a Word from a Trie:

   • Problem: Write a function to delete a word from the Trie. Delete the word "bat" from the Trie created earlier and ensure that the Trie structure is updated correctly.

6. Count the Number of Words in a Trie:

   • Problem: Write a function to count the total number of words stored in the Trie. Use the Trie created earlier and count the total words.

7. Find All Words Stored in a Trie:

   • Problem: Write a function to find and return all words stored in a Trie. Use the Trie created earlier and print all the words stored in it.

8. Find the Longest Word in a Trie:

   • Problem: Write a function to find the longest word stored in a Trie. Use the Trie created earlier and find the longest word.

9. Check if a Trie is Empty:

   • Problem: Write a function to check if a Trie is empty (i.e., contains no words). Use the Trie from previous problems and check its state.

10. Autocomplete Suggestions Using Trie:

    • Problem: Write a function to implement autocomplete suggestions using a Trie. For a given prefix, return all words that can complete the prefix. Use the Trie created earlier and find suggestions for the prefix "ca".

11. Find Words Matching a Pattern in a Trie:

    • Problem: Write a function to find all words in the Trie that match a given pattern where . can represent any character (similar to regular expressions). Use the Trie created earlier and find words matching the patterns "b.ll" and "a.p.e".

12. Find the Shortest Unique Prefix for Each Word in a Trie:

    • Problem: Write a function to find the shortest unique prefix for each word in the Trie. Use the list ["dog", "dove", "duck", "dot"] and find the unique prefixes for each word.

13. Find the Longest Common Prefix Using Trie:

    • Problem: Write a function to find the longest common prefix among a set of words using a Trie. Use the words ["apple", "appetizer", "application", "appetite"] and find the longest common prefix.

14. Insert Multiple Words into a Trie:

    • Problem: Write a function to insert multiple words into the Trie. Insert the words ["hello", "hero", "hill", "heat"] into the Trie and display the structure.

15. Word Count with Prefix in a Trie:

    • Problem: Write a function to count how many words in the Trie start with a given prefix. Use the Trie created earlier and count how many words start with the prefixes "he" and "hi".

16. Find Words with Common Prefix in a Trie:

    • Problem: Write a function to find all words in the Trie that share a common prefix. Use the Trie created earlier and find all words that share the prefix "ho".

17. Build a Trie from a Dictionary:

    • Problem: Write a program to build a Trie from a given dictionary of words. Use the dictionary ["apple", "app", "bat", "ball", "cat", "cap"] and construct a Trie.

18. Check if a Word is a Prefix of Another Word in the Trie:

    • Problem: Write a function to check if a given word is a prefix of any other word stored in the Trie. Use the Trie created earlier and check if "app" is a prefix of any other word.

19. Find All Words of a Specific Length in a Trie:

    • Problem: Write a function to find all words of a given length stored in a Trie. Use the Trie created earlier and find all words of length 3 and 4.

20. Case-Insensitive Search in a Trie:

    • Problem: Write a function to perform case-insensitive searches in a Trie. Use the Trie created earlier and search for the words "Apple", "BaT", and "CAT" in a case-insensitive manner.

21. Count Total Nodes in a Trie:

    • Problem: Write a function to count the total number of nodes (letters) stored in a Trie. Use the Trie created earlier and count the total nodes.

22. Check if Two Tries are Identical:

    • Problem: Write a function to check if two tries are identical in structure and content. Create two Tries with the words ["dog", "cat", "bat"] and check if they are identical.

23. Insert a Sentence into a Trie:

    • Problem: Write a function to insert a sentence into a Trie by treating each word in the sentence as a node. Insert the sentence "the quick brown fox" into the Trie and display its structure.

24. Longest Word with All Prefixes in a Trie:

    • Problem: Write a function to find the longest word in the Trie where every prefix of the word is also present in the Trie. Use the Trie created earlier and find such a word.

25. Delete a Word with Lazy Deletion in a Trie:

    • Problem: Write a function to implement lazy deletion in a Trie. Mark words as deleted without removing nodes. Use the Trie from previous problems and delete "bat" using lazy deletion.

---

16. Binary Indexed Tree (BIT)

1. Basic Binary Indexed Tree Construction:

   • Problem: Write a program to create a Binary Indexed Tree (BIT) for the following array: [1, 3, 5, 7, 9, 11]. Initialize the BIT and display the tree structure.

2. Update an Element in a Binary Indexed Tree:

   • Problem: Write a function to update an element in the Binary Indexed Tree. Change the value at index 3 to 10 in the array [1, 3, 5, 7, 9, 11] and update the BIT accordingly.

3. Range Sum Query in a Binary Indexed Tree:

   • Problem: Write a function to find the sum of elements between two indices in a Binary Indexed Tree. Use the BIT created earlier and find the sum of elements between index 1 and 4.

4. Prefix Sum Query in a Binary Indexed Tree:

   • Problem: Write a function to find the prefix sum up to a given index in a Binary Indexed Tree. Use the BIT created earlier and find the prefix sum up to index 3.

5. Construct a Binary Indexed Tree from an Array:

   • Problem: Write a program to construct a Binary Indexed Tree from the array [5, 3, 7, 9, 6, 2, 4]. Display the tree structure and verify the values.

6. Range Update in a Binary Indexed Tree:

   • Problem: Write a function to perform a range update in a Binary Indexed Tree. Add 3 to all elements between index 1 and 4 in the array [2, 4, 6, 8, 10, 12] and update the BIT accordingly.

7. Range Minimum Query in a Binary Indexed Tree:

   • Problem: Write a function to find the minimum value in a given range using a Binary Indexed Tree. Use the BIT from previous problems and find the minimum value between index 2 and 5.

8. Point Update in a Binary Indexed Tree:

   • Problem: Write a function to perform a point update (change a single element) in a Binary Indexed Tree. Change the value at index 4 to 20 in the array [1, 2, 3, 4, 5] and update the BIT accordingly.

9. Find the Kth Smallest Element Using Binary Indexed Tree:

   • Problem: Write a function to find the k-th smallest element in a sorted array using a Binary Indexed Tree. Use the array [1, 3, 4, 7, 8, 9] and find the 4th smallest element.

10. Range XOR Query in a Binary Indexed Tree:

    • Problem: Write a function to find the XOR of elements in a given range using a Binary Indexed Tree. Use the array [1, 2, 3, 4, 5] and find the XOR of elements between index 1 and 3.

11. Range Sum with Point Update in a Binary Indexed Tree:

    • Problem: Write a function to calculate the sum of elements within a given range and update a specific element in a Binary Indexed Tree. Use the array [1, 3, 5, 7, 9], find the sum of elements between index 2 and 4, and update the value at index 3 to 10.

12. Find the Prefix Sum for Odd Numbers in a Binary Indexed Tree:

    • Problem: Write a function to calculate the prefix sum for all odd numbers in a Binary Indexed Tree. Use the array [2, 3, 5, 6, 8, 9] and find the sum of odd numbers up to index 5.

13. Find the Range Product Using Binary Indexed Tree:

    • Problem: Write a function to calculate the product of elements in a given range using a Binary Indexed Tree. Use the array [1, 2, 3, 4, 5] and find the product of elements between index 1 and 4.

14. Find the Number of Elements Greater than X in a Binary Indexed Tree:

    • Problem: Write a function to count the number of elements greater than a given value x in a specific range using a Binary Indexed Tree. Use the array [10, 20, 30, 40, 50] and find how many elements are greater than 25 between index 1 and 4.

15. Find the Number of Elements Less than X in a Binary Indexed Tree:

    • Problem: Write a function to count the number of elements less than a given value x in a specific range using a Binary Indexed Tree. Use the array [10, 20, 30, 40, 50] and find how many elements are less than 35 between index 0 and 3.

16. Range Sum with Lazy Propagation Using Binary Indexed Tree:

    • Problem: Write a function to calculate the range sum with lazy propagation in a Binary Indexed Tree. Use the array [1, 2, 3, 4, 5], update the range [2, 4] by adding 5 to each element, and find the sum between index 1 and 4.

17. Find the Prefix Sum for Even Numbers in a Binary Indexed Tree:

    • Problem: Write a function to calculate the prefix sum for all even numbers in a Binary Indexed Tree. Use the array [2, 3, 4, 5, 6, 7, 8] and find the sum of even numbers up to index 5.

18. Find the Longest Increasing Subsequence Using Binary Indexed Tree:

    • Problem: Write a function to find the longest increasing subsequence in an array using a Binary Indexed Tree. Use the array [3, 4, 5, 1, 2, 8, 6, 7] and find the length of the longest increasing subsequence.

19. Find the Kth Largest Element Using Binary Indexed Tree:

    • Problem: Write a function to find the k-th largest element in an array using a Binary Indexed Tree. Use the array [1, 3, 5, 7, 9] and find the 3rd largest element.

20. Count the Number of Inversions Using Binary Indexed Tree:

    • Problem: Write a function to count the number of inversions in an array using a Binary Indexed Tree. An inversion is when a larger element appears before a smaller element in the array. Use the array [8, 4, 2, 1] and count the number of inversions.

21. Update Multiple Elements in a Binary Indexed Tree:

    • Problem: Write a function to update multiple elements in a Binary Indexed Tree. Update the elements at indices 1, 3, and 5 by adding 5 to each value in the array [2, 4, 6, 8, 10] and update the BIT accordingly.

22. Find the GCD of Elements in a Range Using Binary Indexed Tree:

    • Problem: Write a function to find the GCD (Greatest Common Divisor) of elements in a given range using a Binary Indexed Tree. Use the array [12, 18, 24, 36] and find the GCD of elements between index 1 and 3.

23. Find the Sum of Prime Numbers Using Binary Indexed Tree:

    • Problem: Write a function to find the sum of prime numbers in a given range using a Binary Indexed Tree. Use the array [2, 3, 4, 5, 6, 7] and find the sum of primes between index 1 and 4.

24. Find the Largest Element Less than or Equal to X Using Binary Indexed Tree:

    • Problem: Write a function to find the largest element that is less than or equal to X in a given range using a Binary Indexed Tree. Use the array [10, 20, 30, 40, 50] and find the largest element less than or equal to 35 between index 1 and 4.

25. Convert a Binary Indexed Tree to a Segment Tree:

    • Problem: Write a function to convert a Binary Indexed Tree into a Segment Tree. Use the array [1, 2, 3, 4, 5] to build a BIT and convert it into a Segment Tree.

---

17. Graph