DSA Cheatsheet for Capgemini by Techie CodeBuddy

(20K Subscribers Free GiveAway)

(Formatting of this document is under process, once it will
done, I will update it)
### What is a Data Structure?
A data structure is a way of organizing, managing, and storing data so that it can
be accessed and modified efficiently. It defines how data is stored, accessed, and
manipulated in a computer system. The choice of data structure can significantly
impact the performance of an algorithm, influencing speed, memory usage, and
simplicity.

### Types of Data Structures:

Data structures can broadly be classified into two categories:
1. Linear Data Structures
2. Non-linear Data Structures

#### 1. Linear Data Structures:

Elements are arranged in a sequential manner, one after another.
- Array :
- Definition : A collection of elements identified by index or key.
Real-World Use Case : Used to store a fixed set of elements such as storing
days of the week or months in a year in an e-commerce website to show dates or
order tracking.

Linked List:
- Definition : A collection of nodes where each node contains data and a
reference to the next node.

Real-World Use Case : Useful for dynamic memory allocation, such as

implementing a photo gallery app where the number of photos is unknown.
Stack :
- Definition : A linear data structure that follows a Last In, First Out (LIFO)
approach.

Real-World Use Case : Browser history and undo/redo operations in text editors
work based on stacks.

Queue :
- Definition : A linear data structure that follows a First In, First Out (FIFO)
approach.
Real-World Use Case : Used in scenarios like ticket booking systems, customer
service systems, or task scheduling in operating systems.

#### 2. Non-Linear Data Structures:

Elements are not arranged in a sequential manner, and one element can be
connected to multiple elements.
Tree :
Definition : A hierarchical structure with a root and nodes where each node
contains data and references to its children.
Real-World Use Case : File systems in computers where files and directories are
organized in a hierarchical structure.

Graph :
Definition : A collection of nodes (vertices) connected by edges, which can be
directed or undirected.
Real-World Use Case : Social networks where users (nodes) are connected by
friendships (edges) or route planning apps like Google Maps.
Hash Table :
Definition : A data structure that maps keys to values using a hash function to
compute an index into an array of buckets.

Real-World Use Case : Used in caching systems like a web browser’s cache or
database indexing.

### Applications of Data Structures in the Real World:

• Arrays : Used in databases to quickly access data by indexing, or in
applications like image processing where pixels are stored as arrays.

• Linked Lists : Efficient in scenarios where frequent insertions and deletions

are required, such as in music players (playlists).

• Stacks : Used in algorithms like depth-first search, recursive function calls,

and balancing parentheses in compilers.
• Queues : Used in print job scheduling, process management in operating
systems, and real-time data streaming applications.

• Trees : Widely used in search algorithms like binary search trees or in

applications like network routers.

• Graphs : Employed in networking algorithms, recommendation systems

(e.g., Netflix), and transportation systems.

• Hash Tables : Common in applications where fast lookups are necessary,

such as in language interpreters and memory management.

These data structures form the foundation of efficient problem-solving in

computer science and are used in countless real-world applications, from simple
programs to large-scale systems like operating systems and databases.

### Major Operations Performed on Data Structures

Operations on data structures are fundamental processes used to manipulate
data stored within the structure. Each operation affects how data is stored,
retrieved, or modified. Below are the common operations applicable to most data
structures:

### 1. Insertion
Definition : Adding an element to the data structure.
▪ Arrays : Adding an element to a specific index.
▪ Linked Lists : Inserting a node at the beginning, end, or between two nodes.
▪ Stacks : Push operation adds an element to the top of the stack.
▪ Queues : Enqueue operation adds an element to the rear of the queue.
▪ Trees : Adding a node at the appropriate location based on the tree's
properties (e.g., Binary Search Tree).
▪ Graphs : Adding an edge between vertices or adding new vertices.
Real-World Example :
➢ Inserting a new product into a catalog (Array).
➢ Adding a webpage to the browsing history (Stack).
➢ Adding a person to the customer support queue (Queue).

### 2. Deletion
Definition : Removing an element from the data structure.
▪ Arrays : Removing an element requires shifting all subsequent
elements.
▪ Linked Lists : Removing a node can be done from the beginning, end, or
in the middle by updating pointers.
▪ Stacks : Pop operation removes the top element.
▪ Queues : Dequeue operation removes the front element.
▪ Trees : Removing a node while maintaining tree properties.
▪ Graphs : Removing an edge between vertices or removing a vertex.

Real-World Example :
➢ Deleting a file from a folder (Tree).
➢ Closing the most recent application window (Stack).
➢ Removing a task from a to-do list (Linked List).
### 3. Traversal
Definition : Visiting each element of the data structure in a systematic way.
▪ Arrays : Iterate through all elements.
▪ Linked Lists : Traverse through nodes from head to tail.
▪ Stacks/Queues : Traverse elements without modifying their order.
▪ Trees : Preorder, inorder, or postorder traversal.
▪ Graphs : Depth-First Search (DFS) or Breadth-First Search (BFS)
algorithms.

Real-World Example :
➢ Going through your photo album (Array).
➢ Checking customer queue to see who is next (Queue).
➢ Navigating through folders and subfolders on your computer (Tree).

### 4. Searching
Definition : Finding the location of a particular element in the data structure.
▪ Arrays : Linear search or Binary search.
▪ Linked Lists : Traverse nodes to find the required data.
▪ Trees : Binary search is often used in Binary Search Trees (BST).
▪ Graphs : Searching for a node or path using BFS or DFS.
Real-World Example :
➢ Searching for a contact in your phone's address book (Array).
➢ Finding a file in a directory (Tree).
➢ Searching for a friend in a social network (Graph).

### 5. Sorting
Definition : Arranging the elements of the data structure in a specific order
(ascending or descending).
▪ Arrays/Lists : Bubble sort, Quick sort, Merge sort, etc.
▪ Linked Lists : Similar sorting algorithms, but modifications are needed
due to pointers.
▪ Trees : In Binary Search Trees, inorder traversal gives sorted elements.
▪ Graphs : Topological sorting for Directed Acyclic Graphs (DAG).

Real-World Example :
➢ Sorting customer data by their last names (Array).
➢ Ranking students based on their exam scores (Array/Linked List).
---

### 6. Merging

Definition : Combining two or more data structures into a single structure.

- Arrays : Merging two sorted arrays.

- Linked Lists : Merging two linked lists into one.
- Trees : Merging Binary Search Trees by combining nodes.
- Graphs : Combining two graphs by uniting vertices and edges.

Example (C++) :
```cpp
int arr1[] = {1, 3, 5};
int arr2[] = {2, 4, 6};
int arr3[6];
merge(arr1, arr1+3, arr2, arr2+3, arr3); // Merging two arrays
```

Real-World Example :
- Merging two sorted lists of employees from two departments.
- Combining data from two databases.

---

### 7. Updation
Definition : Modifying the value of an element at a specific location.

- Arrays : Changing the value at a given index.

- Linked Lists : Updating a node’s data.
- Trees : Updating node values based on certain conditions.
- Graphs : Changing the weight of an edge.

Example (Java) :
```java
arr[2] = 50; // Updating value at index 2
```

Real-World Example :
- Updating the price of a product in a shopping cart.
- Changing the priority of a task in a to-do list.

---

### 8. Accessing

Definition : Retrieving the value of an element at a specific index or position.

- Arrays : Accessing an element by its index.

- Linked Lists : Accessing elements by traversing nodes.
- Trees : Accessing nodes using traversal algorithms.
- Graphs : Accessing vertices or edges.

Example (C++) :
```cpp
int value = arr[2]; // Accessing value at index 2
```

Real-World Example :
- Checking the status of an order in an e-commerce app (Access data from Array).
- Accessing a specific message in a conversation history.

---

### Conclusion:
Understanding these operations helps in choosing the right data structure for
specific tasks. Efficient handling of these operations can significantly enhance
the performance of applications, especially when working with large datasets or
real-time systems.

### Advantages of Using Different Data Structures

Each data structure offers unique advantages that make them suitable for
specific use cases and scenarios. Understanding these advantages can help in
choosing the most efficient data structure for a given problem. Below are the
advantages of various data structures:

---
### 1. Array

Advantages :
- Random Access : Elements can be accessed directly using the index, allowing
constant time complexity \(O(1)\) for accessing elements.
- Memory Efficiency : If the size of the array is known, it uses memory efficiently.
- Cache-Friendly : Elements are stored in contiguous memory locations, making
array traversal faster due to better cache performance.

Use Case : Storing small, fixed-size datasets like a list of months or temperature
readings for the week.

---

### 2. Linked List

Advantages :
- Dynamic Size : Linked lists grow and shrink dynamically as needed without
wasting memory.
- Efficient Insertions/Deletions : Inserting or deleting elements at any position
(especially at the beginning or middle) is more efficient compared to arrays (no
need for shifting elements).
- No Memory Wastage : Memory is allocated only when needed, unlike arrays
where you need to allocate memory upfront.

Use Case : Implementing dynamic applications like a music player playlist or

managing browsing history.
---

### 3. Stack

Advantages :
- Simple and Fast Operations : Operations like push and pop are performed in
constant time \(O(1)\).
- Reversing Nature (LIFO) : Ideal for problems where the last added element is
needed first, like undo operations or browser history.
- Memory Efficiency : Stacks use only the memory required by the current data.

Use Case : Useful in recursion, reversing strings, and evaluating expressions (e.g.,
postfix notation).

---

### 4. Queue

Advantages :
- FIFO Nature : It ensures that the first element added is the first to be removed,
making it suitable for tasks like scheduling.
- Constant Time for Insertions and Deletions : Enqueue and dequeue operations
are performed in \(O(1)\) time.
- Fair Process Handling : Useful in systems that require fair handling of processes,
such as print queues or task scheduling in operating systems.

Use Case : Task scheduling in operating systems, customer service queues, or

simulating real-world scenarios like ticketing systems.
---

### 5. Tree (Binary Tree, Binary Search Tree)

Advantages :
- Efficient Search and Sort : In Binary Search Trees (BST), searching, insertion,
and deletion operations can be done in \(O(\log n)\), making it efficient for
dynamic datasets.
- Hierarchical Structure : Ideal for representing hierarchical data like folder
structures or organizational charts.
- Balancing Capabilities : Advanced trees like AVL or Red-Black Trees are self-
balancing, which ensures that operations remain efficient.

Use Case : File systems, decision-making algorithms (like decision trees), or

representing organizational hierarchies.

---

### 6. Graph

Advantages :
- Modeling Complex Relationships : Graphs can represent complex real-world
systems with various relationships, such as social networks, transport systems, or
recommendation systems.
- Flexible Representation : Vertices (nodes) and edges can represent any entity
and their relationships, making graphs versatile.
- Efficient Traversal : Algorithms like DFS and BFS enable efficient traversal and
searching in large datasets.
Use Case : Social networks (e.g., Facebook friend connections), navigation
systems (e.g., Google Maps), or recommendation systems.

---

### 7. Hash Table

Advantages :
- Fast Access : With a good hash function, accessing elements in a hash table
takes constant time \(O(1)\), making it extremely fast for lookups.
- Efficient Key-Value Pairing : Hash tables allow efficient storage and retrieval of
key-value pairs, making them ideal for situations like database indexing.
- Flexible Storage : Hash tables can handle large datasets dynamically.

Use Case : Caching mechanisms in web browsers, database indexing, or storing

large dictionaries in language processing systems.

---

### 8. Heap (Min Heap / Max Heap)

Advantages :
- Efficient Priority Management : Heaps are used for priority queues where the
smallest or largest element needs to be quickly accessed.
- Efficient Insertions and Deletions : Operations like insertions and deletions
maintain the heap property and take \(O(\log n)\) time.
- Dynamic Data Handling : Like binary trees, heaps grow dynamically without
wasting space.

Use Case : Implementing priority queues for scheduling, Dijkstra’s algorithm for
shortest path finding, and heapsort algorithm.

---

### 9. Trie

Advantages :
- Efficient Searching : Tries offer fast searching and auto-completion features,
especially for strings or dictionaries.
- Prefix-Based Searches : Tries allow searching for a prefix efficiently, making
them ideal for auto-suggestions.
- Memory Efficiency : Although they take more memory upfront, tries are space-
efficient when representing large sets of strings with common prefixes.

Use Case : Implementing dictionaries in search engines, autocomplete features,

or spelling checkers.

---
Choosing the right data structure depends on the specific use case, the size of the
dataset, and the performance requirements for operations like searching,
inserting, or deleting elements.

### What is an Algorithm?

Definition :
An algorithm is a step-by-step procedure or set of rules designed to perform a
specific task or solve a problem. It takes an input, processes it through a series of
well-defined instructions, and produces an output. Algorithms are the backbone
of computer programs and software applications, enabling machines to carry out
tasks automatically and efficiently.
In simpler terms, an algorithm is like a recipe with detailed steps for solving a
problem or completing a task.

---

### Characteristics of a Good Algorithm

A well-designed algorithm should have the following characteristics:

1. Input :
- The algorithm should have well-defined inputs, whether one or more, or even
zero inputs in some cases.

Example : In a sorting algorithm, the input might be an unsorted array of

numbers.

2. Output :
- The algorithm must produce a result or output. The output should be related to
the given inputs and be well-defined.

Example : The sorted array after applying the sorting algorithm is the output.

3. Finiteness :
- The algorithm must terminate after a finite number of steps. It should not go
into an infinite loop.
Example : If an algorithm is designed to find the largest number in a list, it
should eventually stop after going through the list.

4. Definiteness :
- Every step of the algorithm should be clear and unambiguous. Each operation
must be well-defined so that it can be executed without confusion.

Example : "Add 2 to the variable x" is a definite instruction, while "Do something
with x" is ambiguous.

5. Effectiveness :
- An algorithm should be efficient enough to solve the problem using a
reasonable amount of resources (time, memory, etc.). It should provide a solution
using basic operations within the system's capabilities.

Example : A sorting algorithm like quicksort is effective because it generally

provides good performance in most situations.

6. Generality :
- A good algorithm should be applicable to a wide range of problems, not just for
a specific set of inputs. It should be adaptable for different situations.

Example : A general search algorithm should work for arrays of any length and
with various types of data (integers, strings, etc.).

---

### Data Flow of an Algorithm

The data flow in an algorithm represents how data moves from the input phase to
the output, undergoing transformations at each step. Here's a basic flow:

1. Input :
- Data is fed into the algorithm as the starting point. This could be a set of
numbers, strings, or any other type of data.

Example : An unsorted list of numbers as input for a sorting algorithm.

2. Processing (Steps/Instructions) :
- The input data goes through a series of operations based on the defined steps
of the algorithm. This is where the core logic takes place.

Example : The sorting algorithm compares and swaps elements, rearranging

them into order.

3. Intermediate Data (Optional) :

- Sometimes, an algorithm may generate intermediate results that are used in
subsequent steps.

Example : In a merge sort, the algorithm first breaks down the array into smaller
sub-arrays and then merges them back.

4. Output :
- Once the algorithm completes its process, it produces an output that is the
result of the input data after applying the algorithm's steps.

Example : The sorted list of numbers is the final output of the sorting algorithm.
5. Termination :
- The algorithm finishes its execution and stops, ensuring it does not run
indefinitely.

---

### Why Do We Need Algorithms?

1. Efficiency :
- Algorithms allow us to solve problems faster and more efficiently. For example,
searching for an element in a sorted array can be done much quicker using an
algorithm like binary search than by checking each element one by one.

Example : Google search uses sophisticated algorithms to retrieve relevant

information quickly.

2. Automation :
- Algorithms automate complex and repetitive tasks. Computers can follow
these algorithms to execute processes without human intervention, increasing
productivity.

Example : Online shopping platforms use algorithms to suggest products based

on your browsing history.

3. Problem-Solving :
- Algorithms are essential for solving problems in computer science,
mathematics, and many other fields. They break down complicated problems into
manageable steps.
Example : The Dijkstra algorithm is used to find the shortest path between two
points on a map.

4. Optimization :
- Algorithms help optimize systems to perform tasks using fewer resources
(time, memory, etc.). For example, an algorithm can minimize the number of
comparisons or operations needed to achieve the desired outcome.

Example : The QuickSort algorithm is often faster than other sorting methods,
especially for large datasets.

5. Consistency :
- Since algorithms follow a fixed sequence of steps, they consistently produce
the same output for the same input, ensuring accuracy and reliability.

Example : A banking application uses an algorithm to calculate monthly interest

on savings accounts, ensuring consistent results.

6. Scalability :
- Well-designed algorithms can handle larger datasets efficiently, making them
scalable for systems that grow over time.

Example : Social media platforms use algorithms to manage and sort massive
amounts of user data in real-time.

---

### Real-World Example of an Algorithm:

Online Shopping Platform (Product Recommendation Algorithm) :
- Input : User's previous browsing history, product searches, and purchases.
- Processing : The recommendation algorithm analyzes this data, compares it
with similar users' preferences, and identifies patterns.
- Output : Personalized product recommendations for the user, such as "People
who bought this also bought..."
- Termination : The algorithm stops after generating the recommendation list,
ensuring the user doesn’t experience delays in loading time.

---

### Conclusion

An algorithm is critical in both everyday tasks and complex problem-solving

scenarios. Its characteristics (input, output, finiteness, definiteness, etc.) make it
essential for automating and optimizing processes. By understanding the flow and
efficiency of algorithms, we can solve problems faster, handle more significant
data efficiently, and ensure tasks are performed accurately.

### Approaches of Algorithms

Algorithms can be designed using various approaches based on the type of

problem they are trying to solve. Each approach provides a unique strategy for
problem-solving and is selected based on factors like complexity, efficiency, and
resource usage. Here are the most common algorithmic approaches:

---

### 1. Brute Force

Description :
- A brute force approach involves trying all possible solutions to a problem until
the correct one is found. It doesn’t consider optimization and simply explores
every option.

Advantages :
- Simple to understand and implement.
- Guaranteed to find the solution if one exists.

Disadvantages :
- Inefficient for large problems due to high time complexity.

Example :
- String Matching : In a brute-force string matching algorithm, you compare the
pattern with every substring in the text.

```cpp
// C++ example of brute-force string matching
bool bruteForceSearch(string text, string pattern) {
for (int i = 0; i <= text.length() - pattern.length(); i++) {
int j = 0;
while (j < pattern.length() && text[i + j] == pattern[j]) {
j++;
}
if (j == pattern.length()) {
return true; // Pattern found
}
}
return false; // Pattern not found
}
```

---

### 2. Divide and Conquer

Description :
- This approach divides a problem into smaller sub-problems, solves them
independently, and then combines their solutions to get the final result.

Advantages :
- Efficient for large problems.
- Often reduces the time complexity significantly.

Disadvantages :
- Requires recursion, which can increase memory usage due to function calls.

Example :
- Merge Sort : Divide the array into halves, sort each half, and then merge them.

```cpp
// C++ example of Merge Sort using divide and conquer
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int L[n1], R[n2]; // temporary arrays

for (int i = 0; i < n1; i++) L[i] = arr[left + i];

for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}

while (i < n1) arr[k++] = L[i++];

while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```

---

### 3. Dynamic Programming

Description :
- Dynamic programming breaks a problem down into smaller overlapping sub-
problems and solves each sub-problem just once, storing the result for future use
(memoization).

Advantages :
- Avoids recalculating solutions to sub-problems, reducing time complexity.
- Efficient for problems with overlapping sub-problems like optimization tasks.

Disadvantages :
- Can use a lot of memory if the problem space is large (due to storing sub-
problems).

Example :
- Fibonacci Sequence : Using dynamic programming to store previously
calculated Fibonacci numbers.

```cpp
// C++ example of Fibonacci using dynamic programming
int fib(int n) {
int f[n + 2]; // Create an array to store Fibonacci numbers
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
```

---

### 4. Greedy Algorithm

Description :
- A greedy algorithm builds a solution step by step by choosing the locally optimal
choice at each step, hoping to find a global optimum.

Advantages :
- Simple and efficient in certain problems, offering fast solutions.
- Requires fewer resources like memory.

Disadvantages :
- Doesn’t always produce the optimal solution for all problems.

Example :
- Coin Change Problem : Choose the largest denomination first to minimize the
number of coins.
```cpp
// C++ example of greedy algorithm for coin change
int minCoins(int coins[], int n, int amount) {
sort(coins, coins + n, greater<int>()); // Sort coins in decreasing order
int count = 0;
for (int i = 0; i < n; i++) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return count; // Minimum number of coins
}
```

---

### 5. Backtracking

Description :
- Backtracking tries to build a solution incrementally by exploring all possible
options. If a solution fails, it backtracks and tries a different option.

Advantages :
- Useful for constraint satisfaction problems like puzzles.
- Can find all possible solutions, not just one.
Disadvantages :
- Can be slow due to its exhaustive search of all possibilities.

Example :
- N-Queens Problem : Place N queens on an NxN chessboard so no two queens
threaten each other.

```cpp
// C++ example of N-Queens problem using backtracking
bool isSafe(int board[][10], int row, int col, int n) {
for (int i = 0; i < col; i++) if (board[row][i]) return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false;
for (int i = row, j = col; i < n && j >= 0; i++, j--) if (board[i][j]) return false;
return true;
}

bool solveNQueens(int board[][10], int col, int n) {

if (col >= n) return true;
for (int i = 0; i < n; i++) {
if (isSafe(board, i, col, n)) {
board[i][col] = 1;
if (solveNQueens(board, col + 1, n)) return true;
board[i][col] = 0;
}
}
return false;
}
```

---

### 6. Recursive Approach

Description :
- In recursion, a problem is solved by breaking it down into smaller instances of
the same problem. Each smaller instance is solved recursively until a base case is
reached.

Advantages :
- Provides elegant solutions for problems that can be divided into smaller sub-
problems.
- Simplifies complex problems by breaking them down.

Disadvantages :
- Recursive solutions can lead to high memory usage due to function call stacks.
- Not always efficient, especially when overlapping sub-problems exist.

Example :
- Factorial Calculation : Recursive algorithm to calculate the factorial of a
number.

```cpp
// C++ example of factorial using recursion
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
```

---

### 7. Randomized Algorithm

Description :
- Randomized algorithms use random numbers at some point during their process
to make decisions. These algorithms can be used to improve performance or for
probabilistic solutions.

Advantages :
- Can be faster in some cases compared to deterministic algorithms.
- Helps solve problems where deterministic approaches might be too slow.

Disadvantages :
- The result might not always be the same, and sometimes the solution is only
approximate.

Example :
- QuickSort (Randomized Pivot Selection) : Choosing a random pivot to avoid
worst-case performance.
```cpp
// C++ example of randomized quicksort
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high); // Partition index
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
```

---
### Conclusion

Each algorithmic approach has its own advantages and is suited for specific types
of problems. By understanding the characteristics and application of each
approach, you can select the most efficient method for solving a particular
problem.

### Types of Algorithms

Algorithms can be classified into various types based on their functionality, design
methodology, and application area. Here are some of the most common types of
algorithms:

---

### 1. Sorting Algorithms

Description : Sorting algorithms arrange the elements of a list or array in a

specific order (ascending or descending).

Examples :
- Bubble Sort : Simple comparison-based algorithm.
- Quick Sort : Efficient divide-and-conquer sorting algorithm.
- Merge Sort : Sorts by dividing the array and merging the sorted sub-arrays.

Real-World Use Case : Sorting data for display in applications like e-commerce
websites to show products based on price or rating.
```cpp
// C++ example of Bubble Sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}
```

---

### 2. Searching Algorithms

Description : Searching algorithms are used to find a specific element within a

data structure.

Examples :
- Linear Search : Checks each element sequentially until the target is found.
- Binary Search : Efficiently finds an element in a sorted array by repeatedly
dividing the search interval in half.

Real-World Use Case : Searching for a user in a database or finding a book in a

library catalog.
```cpp
// C++ example of Binary Search
int binarySearch(int arr[], int left, int right, int x) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1; // Element not found
}
```

---

### 3. Graph Algorithms

Description : Graph algorithms are used to solve problems related to graph data
structures, where data is represented as nodes and edges.

Examples :
- Dijkstra's Algorithm : Finds the shortest path between nodes in a weighted
graph.
- Depth-First Search (DFS) : Explores as far as possible along each branch before
backtracking.
- Breadth-First Search (BFS) : Explores all neighbors at the present depth prior to
moving on to nodes at the next depth level.

Real-World Use Case : Used in network routing protocols to find the shortest path
for data transmission.

```cpp
// C++ example of Depth-First Search
void DFS(int v, vector<bool>& visited, const vector<vector<int>>& adj) {
visited[v] = true;
cout << v << " ";
for (int i : adj[v]) {
if (!visited[i]) DFS(i, visited, adj);
}
}
```

---

### 4. Dynamic Programming Algorithms

Description : Dynamic programming algorithms solve problems by breaking them

down into simpler sub-problems and storing the results to avoid redundant
calculations.

Examples :
- Fibonacci Sequence : Calculates Fibonacci numbers using memoization.
- Knapsack Problem : Solves optimization problems by selecting items to
maximize value without exceeding capacity.

Real-World Use Case : Used in resource allocation problems, such as scheduling

and budget management.

```cpp
// C++ example of the Fibonacci sequence using dynamic programming
int fib(int n) {
int f[n + 1];
f[0] = 0; f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
```

---

### 5. Greedy Algorithms

Description : Greedy algorithms build a solution step by step, always choosing

the next step that offers the most immediate benefit.

Examples :
- Prim's Algorithm : Finds the minimum spanning tree for a graph.
- Huffman Coding : Constructs an optimal prefix code for data compression.

Real-World Use Case : Used in optimization problems like job scheduling and
network routing.

```cpp
// C++ example of Prim's Algorithm (simplified)
void primsAlgorithm(int graph[V][V]) {
// Implementation to find minimum spanning tree using a greedy approach
}
```

---

### 6. Backtracking Algorithms

Description : Backtracking algorithms try to build a solution incrementally and

abandon solutions that fail to satisfy the constraints of the problem.

Examples :
- N-Queens Problem : Places N queens on an NxN chessboard.
- Sudoku Solver : Solves a Sudoku puzzle.

Real-World Use Case : Used in puzzle solving, game playing, and constraint
satisfaction problems.

```cpp
// C++ example of backtracking in the N-Queens problem
bool solveNQueens(int board[N][N], int col) {
// Recursive function to solve the N-Queens problem
}
```

---

### 7. Randomized Algorithms

Description : Randomized algorithms utilize random numbers to influence the

algorithm's behavior, which can lead to simpler or faster solutions.

Examples :
- Randomized QuickSort : Chooses a random pivot to improve performance.
- Monte Carlo Methods : Uses randomness to solve deterministic problems.

Real-World Use Case : Used in simulations, randomized algorithms in

cryptography, and probabilistic data structures.

```cpp
// C++ example of randomized QuickSort
int randomPartition(int arr[], int low, int high) {
int randomIndex = low + rand() % (high - low);
swap(arr[randomIndex], arr[high]);
return partition(arr, low, high);
}
```

---

### 8. Divide and Conquer Algorithms

Description : Divide and conquer algorithms break a problem into smaller sub-
problems, solve each sub-problem recursively, and combine the results.

Examples :
- Merge Sort : Divides the array, sorts the halves, and merges them.
- Binary Search : Recursively narrows down the search interval.

Real-World Use Case : Used in efficient sorting, searching, and mathematical

computations.

```cpp
// C++ example of Merge Sort (divide and conquer)
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```
---

### Conclusion

Understanding the various types of algorithms allows you to choose the most
appropriate one for solving specific problems efficiently. Each algorithm type has
its strengths, weaknesses, and applications in real-world scenarios.

### Algorithm Complexity

Algorithm complexity helps in analyzing the efficiency of an algorithm in terms of

time and space. It provides insight into how the algorithm's performance scales
with the size of the input. The two main types of complexity are:

1. Time Complexity
2. Space Complexity

---

### 1. Time Complexity

Description : Time complexity measures the amount of time an algorithm takes to

complete as a function of the size of the input. It is often expressed using Big O
notation.

Common Time Complexities :

- O(1) - Constant Time : The algorithm's runtime is constant and does not change
with the input size.
- O(log n) - Logarithmic Time : The algorithm's runtime grows logarithmically with
the input size. Common in binary search algorithms.
- O(n) - Linear Time : The runtime grows linearly with the input size. Common in
simple loops.
- O(n log n) - Linearithmic Time : The runtime grows proportionally to \(n \log n\).
Common in efficient sorting algorithms like Merge Sort and Quick Sort.
- O(n^2) - Quadratic Time : The runtime grows quadratically with the input size.
Common in algorithms with nested loops like Bubble Sort.
- O(2^n) - Exponential Time : The runtime doubles with each additional input
element. Common in certain recursive algorithms like the naive solution to the
Traveling Salesman Problem.
- O(n!) - Factorial Time : The runtime grows factorially with the input size.
Common in brute-force solutions to problems like the Traveling Salesman
Problem.

Example :

```cpp
// C++ example of time complexity O(n) - Linear Time
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " "; // O(n)
}
}
```

---
### 2. Space Complexity

Description : Space complexity measures the amount of memory an algorithm

uses relative to the input size. It helps in understanding how the algorithm scales
with respect to memory usage.

Common Space Complexities :

- O(1) - Constant Space : The memory usage is constant and does not depend on
the input size. Examples include simple iterative algorithms.
- O(n) - Linear Space : The memory usage grows linearly with the input size.
Examples include algorithms that store intermediate results in arrays or lists.
- O(n^2) - Quadratic Space : The memory usage grows quadratically with the
input size. Examples include algorithms that use 2D arrays.

Example :

```cpp
// C++ example of space complexity O(n) - Linear Space
void createArray(int size) {
int* arr = new int[size]; // Memory usage grows linearly with size
// Array operations
delete[] arr; // Free allocated memory
}
```

---
### 3. Big O Notation

Big O notation provides an upper bound on the time complexity or space

complexity of an algorithm. It describes the worst-case scenario in terms of the
growth rate of the runtime or memory usage as the input size increases.

Examples :
- O(1) : The algorithm runs in constant time, regardless of input size.
- O(n) : The runtime or memory usage grows linearly with input size.
- O(n^2) : The runtime or memory usage grows quadratically with input size.
- O(log n) : The runtime or memory usage grows logarithmically with input size.

Example :

```cpp
// C++ example of Big O Notation
void constantTimeOperation() {
int x = 10; // O(1) - Constant Time
}

void linearTimeOperation(int n) {
for (int i = 0; i < n; i++) {
// O(n) - Linear Time
}
}

void quadraticTimeOperation(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// O(n^2) - Quadratic Time
}
}
}

void logarithmicTimeOperation(int n) {
while (n > 1) {
n /= 2; // O(log n) - Logarithmic Time
}
}
```

---

### 4. Amortized Analysis

Description : Amortized analysis provides an average time complexity for a

sequence of operations over a data structure. It is useful for understanding the
average performance of an algorithm over time, rather than in a single operation.

Example :
- Dynamic Array : Appending to a dynamic array is an O(1) operation on average,
even though resizing the array may take O(n) time occasionally. The average cost
per operation is amortized to O(1).
```cpp
// C++ example of amortized analysis with dynamic array
void append(int* &arr, int &size, int &capacity, int value) {
if (size == capacity) {
// Resize array
capacity *= 2;
int* newArr = new int[capacity];
for (int i = 0; i < size; i++) newArr[i] = arr[i];
delete[] arr;
arr = newArr;
}
arr[size++] = value; // O(1) on average
}
```

---

### Conclusion

Understanding algorithm complexity helps in evaluating and comparing the

efficiency of different algorithms. By analyzing both time and space complexity,
you can select or design algorithms that best meet the needs of your application
in terms of performance and resource usage.

### Asymptotic Analysis

Asymptotic analysis is a method used to describe the behavior of algorithms as
the size of the input grows toward infinity. It provides a way to evaluate the
efficiency of an algorithm in terms of time and space complexity by focusing on
the growth rate of the algorithm's resource requirements.

---

### Key Concepts

1. Big O Notation (O) :

- Definition : Represents the upper bound of an algorithm's running time or
space requirements. It describes the worst-case scenario.
- Usage : Used to express the maximum time or space an algorithm will take as a
function of the input size.
- Example : `O(n)` indicates that the time or space grows linearly with the input
size.

Example in C++ :
```cpp
// C++ example of Big O Notation O(n)
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // O(n) - Linear Time
}
}
```

2. Big Ω Notation (Ω) :

- Definition : Represents the lower bound of an algorithm's running time or
space requirements. It describes the best-case scenario.
- Usage : Used to express the minimum time or space an algorithm will take.
- Example : `Ω(n)` indicates that the algorithm will require at least linear time or
space.

Example in Java :
```java
// Java example of Big Ω Notation Ω(n)
public void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // Ω(n) - Linear Time
}
}
```

3. Big Θ Notation (Θ) :

- Definition : Represents the tight bound of an algorithm's running time or space
requirements. It describes both the upper and lower bounds.
- Usage : Used to express that the time or space complexity is exactly
proportional to a function.
- Example : `Θ(n)` indicates that the algorithm's time or space grows linearly
with the input size.

Example in C++ :
```cpp
// C++ example of Big Θ Notation Θ(n)
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // Θ(n) - Linear Time
}
}
```

4. Little o Notation (o) :

- Definition : Represents an upper bound that is not tight. It describes the
asymptotic behavior of an algorithm that grows slower than a given function.
- Usage : Used to express that the growth rate of the algorithm is strictly less
than a given rate.
- Example : `o(n^2)` indicates that the algorithm's growth rate is less than
quadratic time but not necessarily linear.

Example : If an algorithm runs in `o(n^2)`, it could be `O(n log n)`.

5. Little ω Notation (ω) :

- Definition : Represents a lower bound that is not tight. It describes the
asymptotic behavior of an algorithm that grows faster than a given function.
- Usage : Used to express that the growth rate of the algorithm is strictly greater
than a given rate.
- Example : `ω(n)` indicates that the algorithm's growth rate is more than linear
time but not necessarily quadratic.

Example : If an algorithm runs in `ω(n)`, it could be `Ω(n log n)`.

---
### Examples and Applications

1. Constant Time (O(1)) :

- Definition : The algorithm's performance is constant and does not change with
the size of the input.
- Example : Accessing an element in an array by index.

```cpp
// C++ example of O(1) - Constant Time
int getElement(int arr[], int index) {
return arr[index]; // O(1) - Constant Time
}
```

2. Linear Time (O(n)) :

- Definition : The algorithm's performance grows linearly with the size of the
input.
- Example : Finding the maximum element in an array.

```cpp
// C++ example of O(n) - Linear Time
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
return max; // O(n) - Linear Time
}
```

3. Quadratic Time (O(n^2)) :

- Definition : The algorithm's performance grows quadratically with the size of
the input.
- Example : Bubble Sort.

```cpp
// C++ example of O(n^2) - Quadratic Time
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}
```

4. Logarithmic Time (O(log n)) :

- Definition : The algorithm's performance grows logarithmically with the size of
the input.
- Example : Binary Search.

```cpp
// C++ example of O(log n) - Logarithmic Time
int binarySearch(int arr[], int left, int right, int x) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1; // Element not found
}
```

---

### Conclusion

Asymptotic analysis provides a way to evaluate and compare algorithms based on

their efficiency in handling large input sizes. By understanding Big O, Big Ω, Big Θ,
Little o, and Little ω notations, you can assess the performance of algorithms and
choose the most suitable one for your needs.

### Arrays

Definition : An array is a data structure that stores a collection of elements, each

identified by an index or key. The elements are stored in contiguous memory
locations, allowing efficient access and modification.
---

### Types of Arrays

1. One-Dimensional Array :
- Description : A simple list of elements where each element is accessed by a
single index.
- Example : A list of integers.

```cpp
// C++ example of a one-dimensional array
int arr[5] = {1, 2, 3, 4, 5};
```

2. Two-Dimensional Array :
- Description : An array of arrays, where elements are accessed by two indices
(row and column).
- Example : A matrix.

```cpp
// C++ example of a two-dimensional array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
```
3. Multi-Dimensional Array :
- Description : Arrays with more than two dimensions. Often used in complex
data representations.
- Example : A 3D matrix.

```cpp
// C++ example of a three-dimensional array
int cube[2][2][2] = {
{
{1, 2},
{3, 4}
},
{
{5, 6},
{7, 8}
}
};
```

4. Dynamic Array :
- Description : An array whose size can be changed during runtime.
Implemented using pointers and dynamic memory allocation.
- Example : Using `new` in C++.

```cpp
// C++ example of a dynamic array
int* dynamicArr = new int[5]; // Create an array of size 5
// Remember to free memory
delete[] dynamicArr;
```

---

### Properties of Arrays

1. Contiguous Memory Allocation : Elements are stored in contiguous memory

locations, allowing for efficient indexing.
2. Fixed Size : In static arrays, the size must be defined at compile time. In
dynamic arrays, the size can be adjusted at runtime.
3. Indexed Access : Elements are accessed using indices, providing constant
time complexity O(1) for access.
4. Homogeneous Elements : All elements in an array are of the same data type.

---

### Notation

- Index : The position of an element in an array. In most programming languages,

indices start at 0.
- Example: For an array `arr[5]`, the valid indices are 0 to 4.
- Size : The number of elements that the array can hold.
- Example: `int arr[5]` has a size of 5.
---

### Operations on Arrays

1. Accessing Elements :
- Description : Retrieve the value of an element using its index.
- Example :

```cpp
// C++ example of accessing an array element
int arr[5] = {1, 2, 3, 4, 5};
int value = arr[2]; // Accesses the element at index 2 (value is 3)
```

2. Inserting Elements :
- Description : Add an element at a specific index (for static arrays, this requires
shifting elements).
- Example : Inserting into a dynamic array.

```cpp
// C++ example of inserting into a dynamic array
int* dynamicArr = new int[6]; // New size 6
// Copy old array to new array
for (int i = 0; i < 5; i++) dynamicArr[i] = arr[i];
dynamicArr[5] = 6; // Insert new element
delete[] arr; // Free old array memory
```
3. Deleting Elements :
- Description : Remove an element and shift the remaining elements to fill the
gap.
- Example : Deleting from a dynamic array.

```cpp
// C++ example of deleting from a dynamic array
int* newArr = new int[4]; // New size 4
for (int i = 0; i < 4; i++) newArr[i] = dynamicArr[i];
delete[] dynamicArr; // Free old array memory
```

4. Updating Elements :
- Description : Modify the value of an element at a specific index.
- Example :

```cpp
// C++ example of updating an array element
int arr[5] = {1, 2, 3, 4, 5};
arr[2] = 10; // Update element at index 2 to 10
```

5. Traversing :
- Description : Iterate through each element of the array to perform operations
like printing or summing.
- Example :
```cpp
// C++ example of traversing an array
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
cout << arr[i] << " "; // Print each element
}
```

---

### Conclusion

Arrays are a fundamental data structure used to store collections of elements.

They provide efficient indexing, but their fixed size (for static arrays) can be a
limitation. Understanding the different types, properties, and operations
associated with arrays helps in selecting and implementing the right data
structure for various problems.

### Advantages and Disadvantages of Arrays

Arrays are fundamental data structures used to store collections of elements.

Here’s a breakdown of their advantages and disadvantages:

---

### Advantages of Arrays

1. Efficient Access :
- Description : Arrays provide constant-time access to elements using their
index. This means that accessing any element in the array takes O(1) time.
- Example : If you have an array `arr[10]`, accessing `arr[5]` is done in constant
time.

2. Contiguous Memory Allocation :

- Description : Arrays store elements in contiguous memory locations, which
leads to better cache performance and reduced overhead for accessing
elements.
- Example : Iterating over an array can be faster due to spatial locality.

3. Simple and Easy to Implement :

- Description : Arrays are straightforward to understand and use, making them
easy to implement and work with.
- Example : Declaring and using arrays in most programming languages involves
simple syntax.

4. Indexing :
- Description : Arrays allow direct indexing, meaning you can access any
element directly by its index, which is useful for operations requiring random
access.
- Example : For an array `arr` with size `n`, accessing `arr[i]` is direct and fast.

5. Memory Efficiency :
- Description : Since arrays use contiguous memory locations, there’s minimal
overhead compared to more complex data structures.
- Example : In contrast to linked lists, arrays do not require additional memory
for storing pointers.

---

### Disadvantages of Arrays

1. Fixed Size :
- Description : The size of an array must be defined at compile time for static
arrays, or it requires manual resizing for dynamic arrays. This can lead to
inefficient memory usage if the size is not well-estimated.
- Example : If you allocate an array of size 100, but only use 50 elements, you
waste memory.

2. Costly Insertion and Deletion :

- Description : Inserting or deleting elements in an array can be costly because it
may require shifting elements, which takes O(n) time.
- Example : Inserting an element at the beginning of an array requires shifting all
subsequent elements.

3. Memory Waste :
- Description : If the array is too large and not fully utilized, it results in memory
waste. Conversely, if the array is too small, you may need to create a new larger
array and copy the elements over.
- Example : A large array with many unused slots consumes more memory than
necessary.

4. Difficulty with Dynamic Resizing :

- Description : Resizing an array is not straightforward and usually involves
creating a new array and copying elements from the old array to the new one.
- Example : When the capacity of a dynamic array is exceeded, a new larger
array must be created, and elements copied over, which is inefficient.

5. Limited Flexibility :
- Description : Arrays lack flexibility in terms of resizing and adding elements
dynamically compared to other data structures like linked lists.
- Example : You cannot directly append an element to a fixed-size array without
creating a new array.

---

### Summary

Arrays are a versatile and efficient data structure for situations where the number
of elements is known in advance and doesn't change frequently. They offer fast
access and efficient memory usage but come with limitations such as fixed size
and costly operations for insertion and deletion. Choosing the right data structure
often depends on the specific requirements of your application, including how
dynamic your data needs to be.

### 2D Arrays / Matrix

Definition : A two-dimensional array (2D array) or matrix is a collection of

elements arranged in a grid-like structure with rows and columns. Each element
is accessed using a pair of indices: one for the row and one for the column.

---
### Properties of 2D Arrays

1. Rectangular Layout :
- Description : Elements are stored in a rectangular grid with a fixed number of
rows and columns.
- Example : A 3x3 matrix has 3 rows and 3 columns.

2. Contiguous Memory Allocation :

- Description : Elements are stored in contiguous memory locations, with rows
stored one after another.
- Example : In memory, a 3x3 matrix is stored as a single block of memory.

3. Indexing :
- Description : Accessing elements requires two indices: one for the row and
one for the column.
- Example : `matrix[i][j]` where `i` is the row index and `j` is the column index.

4. Fixed Size :
- Description : The size of the matrix (number of rows and columns) is typically
fixed at the time of declaration.
- Example : A matrix declared as `int matrix[3][3]` cannot change its size
dynamically.

---

### Notation
- Matrix Representation : A matrix is often represented in mathematical notation
as:
\[
\begin{bmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} & a_{33}
\end{bmatrix}
\]
where \(a_{ij}\) represents the element at row \(i\) and column \(j\).

- Indexing : Elements are accessed using zero-based indexing (in most

programming languages).
- Example : `matrix[0][0]` accesses the element in the first row and first column.

---

### Operations on 2D Arrays

1. Accessing Elements :
- Description : Retrieve the value of an element using its row and column
indices.
- Example :

```cpp
// C++ example of accessing an element in a 2D array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int value = matrix[1][2]; // Accesses the element at row 1, column 2 (value is 6)
```

2. Inserting Elements :
- Description : Insert a new element at a specific location in the matrix.
- Example :

```cpp
// C++ example of inserting an element in a 2D array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
matrix[2][1] = 10; // Update element at row 2, column 1 to 10
```

3. Deleting Elements :
- Description : Removing an element involves setting it to a default value (e.g., 0)
since matrix size is fixed.
- Example :

```cpp
// C++ example of deleting an element in a 2D array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
matrix[1][1] = 0; // Set element at row 1, column 1 to 0
```

4. Traversing :
- Description : Iterate over each element in the matrix to perform operations
such as printing or summing.
- Example :

```cpp
// C++ example of traversing a 2D array
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << matrix[i][j] << " "; // Print each element
}
cout << endl;
}
```

---

### Applications of 2D Arrays / Matrices

1. Mathematical Operations :
- Example : Used in linear algebra for operations such as matrix multiplication,
determinant calculation, and solving systems of linear equations.

```cpp
// C++ example of matrix addition
void addMatrices(int A[3][3], int B[3][3], int result[3][3]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
result[i][j] = A[i][j] + B[i][j];
}
}
}
```

2. Image Processing :
- Example : Images are represented as matrices of pixel values, where each
pixel's color is represented by values in a 2D array.

3. Game Development :
- Example : Used to represent game boards, such as in chess or tic-tac-toe,
where each cell in the grid can hold game state information.

4. Data Tables :
- Example : 2D arrays can represent tables of data, such as spreadsheets or
databases, where rows and columns represent different data attributes.

5. Dynamic Programming :
- Example : 2D arrays are often used in dynamic programming algorithms for
problems like matrix chain multiplication or longest common subsequence.

---

### Conclusion

2D arrays (matrices) are versatile data structures useful for a wide range of
applications, from mathematical computations to image processing. They offer
efficient access and straightforward implementation but come with limitations
like fixed size and lack of flexibility compared to more advanced data structures.
Understanding how to use and manipulate 2D arrays effectively can help solve
many practical problems.

### Strings

Definition : A string is a sequence of characters treated as a single data type.

Strings are commonly used for handling and manipulating text in programming.

---
### Properties of Strings

1. Immutable or Mutable :
- Description : In some languages (e.g., Java), strings are immutable, meaning
they cannot be changed after creation. In others (e.g., C++), strings are mutable.
- Example : In Java, modifying a string creates a new string, whereas in C++, you
can directly modify characters in a `char` array.

2. Indexed Access :
- Description : Characters in a string can be accessed using indices, typically
starting from 0.
- Example : In the string `"Hello"`, `'H'` is at index 0, `'e'` at index 1, and so on.

3. Variable Length :
- Description : Strings can vary in length. The length is usually managed by the
language or data structure.
- Example : The length of `"Hello"` is 5, while `"Hi"` has a length of 2.

---

### Common String Operations

1. Concatenation :
- Description : Joining two or more strings together.
- Example :
```cpp
// C++ example of concatenation
std::string str1 = "Hello, ";
std::string str2 = "World!";
std::string result = str1 + str2; // "Hello, World!"
```

```java
// Java example of concatenation
String str1 = "Hello, ";
String str2 = "World!";
String result = str1 + str2; // "Hello, World!"
```

2. Substring Extraction :
- Description : Extracting a portion of the string.
- Example :

```cpp
// C++ example of substring extraction
std::string str = "Hello, World!";
std::string sub = str.substr(0, 5); // "Hello"
```

```java
// Java example of substring extraction
String str = "Hello, World!";
String sub = str.substring(0, 5); // "Hello"
```

3. Searching :
- Description : Finding the position of a substring or character.
- Example :

```cpp
// C++ example of searching
std::string str = "Hello, World!";
size_t pos = str.find("World"); // 7 (position of "World")
```

```java
// Java example of searching
String str = "Hello, World!";
int pos = str.indexOf("World"); // 7 (position of "World")
```

4. Replacing :
- Description : Replacing occurrences of a substring with another substring.
- Example :

```cpp
// C++ example of replacing
std::string str = "Hello, World!";
std::string newStr = std::regex_replace(str, std::regex("World"), "Universe"); //
"Hello, Universe!"
```

```java
// Java example of replacing
String str = "Hello, World!";
String newStr = str.replace("World", "Universe"); // "Hello, Universe!"
```

5. Splitting :
- Description : Dividing a string into substrings based on a delimiter.
- Example :

```cpp
// C++ example of splitting using stringstream
#include <sstream>
#include <vector>

std::string str = "Hello,World,Universe";

std::stringstream ss(str);
std::string item;
std::vector<std::string> tokens;

while (std::getline(ss, item, ',')) {

tokens.push_back(item);
}
```

```java
// Java example of splitting
String str = "Hello,World,Universe";
String[] tokens = str.split(","); // ["Hello", "World", "Universe"]
```

6. Trimming :
- Description : Removing whitespace from the beginning and end of a string.
- Example :

```cpp
// C++ example of trimming (requires external library like Boost)
std::string str = " Hello, World! ";
str.erase(0, str.find_first_not_of(' ')); // "Hello, World! "
str.erase(str.find_last_not_of(' ') + 1); // "Hello, World!"
```

```java
// Java example of trimming
String str = " Hello, World! ";
String trimmed = str.trim(); // "Hello, World!"
```
---

### String Manipulation Techniques

1. String Builder/Buffer :
- Description : Used to efficiently manipulate strings, especially when frequent
modifications are needed.
- Example :

```cpp
// C++ example using std::ostringstream
#include <sstream>
std::ostringstream oss;
oss << "Hello" << ", " << "World!";
std::string result = oss.str(); // "Hello, World!"
```

```java
// Java example using StringBuilder
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(", ");
sb.append("World!");
String result = sb.toString(); // "Hello, World!"
```

2. String Formatting :
- Description : Formatting strings using placeholders or formatting functions.
- Example :

```cpp
// C++ example of string formatting using std::sprintf
char buffer[50];
std::sprintf(buffer, "Hello, %s!", "World");
std::string result = buffer; // "Hello, World!"
```

```java
// Java example of string formatting
String result = String.format("Hello, %s!", "World"); // "Hello, World!"
```

3. Regular Expressions :
- Description : Used for pattern matching and text manipulation.
- Example :

```cpp
// C++ example of using regular expressions
#include <regex>
std::string str = "Hello, World!";
std::regex reg("World");
bool found = std::regex_search(str, reg); // true
```
```java
// Java example of using regular expressions
import java.util.regex.*;

String str = "Hello, World!";

Pattern pattern = Pattern.compile("World");
Matcher matcher = pattern.matcher(str);
boolean found = matcher.find(); // true
```

---

### Applications of Strings

1. Text Processing :
- Example : Used in text editors, word processors, and any application requiring
text manipulation.

2. Data Serialization :
- Example : Strings are used to serialize data for storage or transmission, such
as in JSON or XML formats.

3. User Input :
- Example : Handling and validating user input from forms or command-line
interfaces.
4. Communication Protocols :
- Example : Strings are used in network protocols to encode and decode
messages.

5. Search Engines :
- Example : String manipulation and pattern matching are essential for search
and indexing algorithms.

---

### Conclusion

Strings are a crucial data type in programming used for handling text. They offer
various operations and manipulations, from basic concatenation to complex
regular expression processing. Understanding how to work with strings efficiently
can greatly enhance text processing capabilities in software development.

### Linked Lists

Definition : A linked list is a linear data structure where each element (node)
points to the next element in the sequence. Unlike arrays, linked lists are not
stored in contiguous memory locations, which allows for dynamic memory
allocation.

---

### Types of Linked Lists

1. Singly Linked List :
- Description : Each node has a single pointer pointing to the next node. The last
node points to `NULL`.
- Example :
```
Head -> [Data|Next] -> [Data|Next] -> [Data|NULL]
```

2. Doubly Linked List :

- Description : Each node has two pointers: one pointing to the next node and
one to the previous node.
- Example :
```
NULL <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> NULL
```

3. Circular Linked List :

- Description : The last node points back to the first node, forming a circle. It can
be singly or doubly circular.
- Example :
```
Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -+
^ |
+-----------------------------------------------+
```

4. Doubly Circular Linked List :

- Description : A circular version of the doubly linked list, where the last node
points back to the first node, and the first node points back to the last node.
- Example :
```
+-> [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -+
| |
+----------------------------------------------------------------+
```

---

### Operations on Linked Lists

1. Insertion :
- Description : Adding a new node at the beginning, end, or a specific position in
the list.
- Code Example :

```cpp
// C++ example of inserting at the beginning of a singly linked list
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(NULL) {}
};

void insertAtBeginning(Node*& head, int newData) {

Node* newNode = new Node(newData);
newNode->next = head;
head = newNode;
}
```

```java
// Java example of inserting at the beginning of a singly linked list
class Node {
int data;
Node next;
Node(int val) {
data = val;
next = null;
}
}

void insertAtBeginning(Node head, int newData) {

Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
```

2. Deletion :
- Description : Removing a node from the list by updating pointers.
- Code Example :

```cpp
// C++ example of deleting a node in a singly linked list
void deleteNode(Node*& head, int key) {
Node* temp = head;
Node* prev = NULL;

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

head = temp->next;
delete temp;
return;
}

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

prev = temp;
temp = temp->next;
}

if (temp == NULL) return;

prev->next = temp->next;
delete temp;
}
```
```java
// Java example of deleting a node in a singly linked list
void deleteNode(Node head, int key) {
Node temp = head;
Node prev = null;

if (temp != null && temp.data == key) {

head = temp.next;
return;
}

while (temp != null && temp.data != key) {

prev = temp;
temp = temp.next;
}

if (temp == null) return;

prev.next = temp.next;
}
```

3. Traversal :
- Description : Visiting each node in the list to perform an operation, such as
printing.
- Code Example :
```cpp
// C++ example of traversing a singly linked list
void traverseList(Node* head) {
Node* temp = head;
while (temp != NULL) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
```

```java
// Java example of traversing a singly linked list
void traverseList(Node head) {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
```

4. Searching :
- Description : Finding a node with a specific value.
- Code Example :

```cpp
// C++ example of searching in a singly linked list
bool search(Node* head, int key) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == key) return true;
temp = temp->next;
}
return false;
}
```

```java
// Java example of searching in a singly linked list
boolean search(Node head, int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) return true;
temp = temp.next;
}
return false;
}
```
---

### Advantages of Linked Lists

1. Dynamic Size :
- Description : Linked lists can easily grow or shrink in size by adding or
removing nodes, which is not possible with arrays.
- Example : Linked lists can handle variable-sized data structures efficiently.

2. Ease of Insertions/Deletions :
- Description : Insertion and deletion operations are more efficient compared to
arrays, especially for operations at the beginning or middle of the list.
- Example : Adding an element to the front of a linked list is an O(1) operation.

3. No Wasted Memory :
- Description : Linked lists use only as much memory as needed, unlike arrays
that may waste space if the allocated size is not fully used.
- Example : A linked list only allocates memory for the nodes it contains.

---

### Disadvantages of Linked Lists

1. Memory Overhead :
- Description : Each node requires extra memory for storing pointers
(next/previous), which can lead to overhead compared to arrays.
- Example : Each node in a linked list has additional space for storing pointers.
2. Sequential Access :
- Description : Linked lists do not support direct access to elements; traversal is
required to access a specific node.
- Example : To access the 10th element, you must traverse from the head to the
10th node.

3. Pointer Complexity :
- Description : Managing pointers can be complex and error-prone, leading to
potential issues such as memory leaks or dangling pointers.
- Example : Incorrect pointer manipulation can lead to segmentation faults or
memory corruption.

---

### Use Cases of Linked Lists

1. Dynamic Memory Allocation :

- Example : Used in scenarios where the size of the data structure is unknown
and varies over time, such as implementing dynamic queues and stacks.

2. Implementation of Other Data Structures :

- Example : Used as the basis for implementing more complex data structures
like graphs, hash tables, and various types of queues and stacks.

3. Real-time Systems :
- Example : Suitable for real-time systems where predictable memory usage and
frequent insertions/deletions are required.
4. Memory Efficient Data Structures :
- Example : Used in environments with limited memory where efficient use of
space is critical, such as embedded systems.

---

### Conclusion

Linked lists are a versatile data structure suitable for applications requiring
dynamic memory allocation and frequent insertions or deletions. They offer
advantages in flexibility and ease of modification but come with trade-offs in
terms of memory usage and access time. Understanding how to implement and
use linked lists effectively can enhance your ability to solve various programming
problems efficiently.

### Stack

Definition : A stack is a linear data structure that follows the Last In, First Out
(LIFO) principle. This means that the most recently added element is the first one
to be removed. It can be visualized as a collection of items stacked on top of each
other, where only the top item is accessible for operations.

---

### Operations on a Stack

1. Push :
- Description : Adds an element to the top of the stack.
- Code Example :

```cpp
// C++ example of push operation
#include <stack>

std::stack<int> s;
s.push(10); // Pushes 10 onto the stack
s.push(20); // Pushes 20 onto the stack
```

```java
// Java example of push operation
import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(10); // Pushes 10 onto the stack
stack.push(20); // Pushes 20 onto the stack
```

2. Pop :
- Description : Removes and returns the top element of the stack. If the stack is
empty, it may cause an error or exception.
- Code Example :

```cpp
// C++ example of pop operation
if (!s.empty()) {
int top = s.top(); // Gets the top element
s.pop(); // Removes the top element
}
```

```java
// Java example of pop operation
if (!stack.isEmpty()) {
int top = stack.peek(); // Gets the top element
stack.pop(); // Removes the top element
}
```

3. Peek (or Top) :

- Description : Returns the top element without removing it.
- Code Example :

```cpp
// C++ example of peek operation
if (!s.empty()) {
int top = s.top(); // Gets the top element
}
```
```java
// Java example of peek operation
if (!stack.isEmpty()) {
int top = stack.peek(); // Gets the top element
}
```

4. IsEmpty :
- Description : Checks if the stack is empty.
- Code Example :

```cpp
// C++ example of isEmpty operation
bool isEmpty = s.empty(); // Returns true if the stack is empty
```

```java
// Java example of isEmpty operation
boolean isEmpty = stack.isEmpty(); // Returns true if the stack is empty
```

---

### Advantages of Stacks

1. Simple Operations :
- Description : Stack operations (push, pop, and peek) are straightforward and
efficient.
- Example : Implementing undo functionality in software.

2. Efficient Memory Usage :

- Description : Stacks manage memory efficiently, with a clear structure for
addition and removal of elements.
- Example : Function call management in recursion.

3. Supports Recursion :
- Description : Stacks are used to implement recursive function calls,
maintaining the state of each function call.
- Example : Function calls and returns in programming languages.

4. Easy to Implement :
- Description : Stacks can be easily implemented using arrays or linked lists.
- Example : Stack data structures are used in various algorithms and
applications.

---

### Disadvantages of Stacks

1. Limited Access :
- Description : Only the top element is accessible; other elements cannot be
accessed directly.
- Example : Cannot retrieve elements below the top without removing them first.
2. Fixed Size (for Array-based Implementation) :
- Description : In array-based stacks, the size of the stack is fixed and cannot
grow beyond its allocated size.
- Example : Stack overflow may occur if the stack exceeds its allocated size.

3. Stack Overflow :
- Description : If the stack exceeds its maximum capacity (in array-based
implementations), it may cause a stack overflow.
- Example : Recursion depth exceeding stack size can cause runtime errors.

---

### Use Cases of Stacks

1. Function Call Management :

- Description : Stacks are used to manage function calls and local variables in
recursive programming.
- Example : Function calls are pushed onto the stack and popped off when
completed.

2. Expression Evaluation :
- Description : Stacks are used to evaluate expressions and manage operators in
infix, prefix, and postfix notations.
- Example : Expression evaluation in calculators and compilers.

3. Undo Mechanism :
- Description : Stacks can be used to implement undo functionality in software
applications.
- Example : Text editors use stacks to undo previous actions.

4. Backtracking Algorithms :
- Description : Stacks are used in algorithms that require backtracking to explore
all possible solutions.
- Example : Depth-first search (DFS) in graphs and solving puzzles like Sudoku.

5. Parsing Syntax :
- Description : Stacks are used in parsing algorithms to validate and process
syntax in programming languages.
- Example : Checking for balanced parentheses and parsing expressions in
compilers.

---

### Conclusion

Stacks are fundamental data structures that support LIFO operations, making
them ideal for tasks involving sequential processing, recursion, and managing
function calls. Their simplicity and efficiency make them widely used in various
applications, from basic programming tasks to complex algorithms.
Understanding stacks and their operations can enhance your ability to implement
and solve a range of computational problems effectively.

### Queue
Definition : A queue is a linear data structure that follows the First In, First Out
(FIFO) principle. This means that the first element added to the queue will be the
first one to be removed. It can be visualized as a collection of items arranged in a
sequence, where elements are added at the rear and removed from the front.

---

### Operations on a Queue

1. Enqueue :
- Description : Adds an element to the rear (end) of the queue.
- Code Example :

```cpp
// C++ example of enqueue operation using std::queue
#include <queue>

std::queue<int> q;
q.push(10); // Adds 10 to the rear of the queue
q.push(20); // Adds 20 to the rear of the queue
```

```java
// Java example of enqueue operation using java.util.Queue
import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>();
queue.add(10); // Adds 10 to the rear of the queue
queue.add(20); // Adds 20 to the rear of the queue
```

2. Dequeue :
- Description : Removes and returns the element from the front of the queue. If
the queue is empty, it may cause an error or exception.
- Code Example :

```cpp
// C++ example of dequeue operation
if (!q.empty()) {
int front = q.front(); // Gets the front element
q.pop(); // Removes the front element
}
```

```java
// Java example of dequeue operation
if (!queue.isEmpty()) {
int front = queue.poll(); // Gets and removes the front element
}
```

3. Peek (or Front) :

- Description : Returns the element at the front of the queue without removing it.
- Code Example :

```cpp
// C++ example of peek operation
if (!q.empty()) {
int front = q.front(); // Gets the front element
}
```

```java
// Java example of peek operation
if (!queue.isEmpty()) {
int front = queue.peek(); // Gets the front element
}
```

4. IsEmpty :
- Description : Checks if the queue is empty.
- Code Example :

```cpp
// C++ example of isEmpty operation
bool isEmpty = q.empty(); // Returns true if the queue is empty
```

```java
// Java example of isEmpty operation
boolean isEmpty = queue.isEmpty(); // Returns true if the queue is empty
```

---

### Advantages of Queues

1. FIFO Order :
- Description : Maintains the order of elements, ensuring that elements are
processed in the order they are added.
- Example : Task scheduling and job processing where tasks are handled in the
order they arrive.

2. Efficient for Certain Operations :

- Description : Enqueue and dequeue operations are efficient, especially with
linked list-based implementations.
- Example : Managing requests in a server queue or tasks in a printer queue.

3. Useful for Buffers :

- Description : Queues are used in buffering data between processes or in
communication systems.
- Example : I/O buffers and data streaming between producers and consumers.

4. Implementation of Other Data Structures :

- Description : Queues are used as building blocks for other data structures and
algorithms.
- Example : Implementing deques (double-ended queues) and priority queues.
---

### Disadvantages of Queues

1. Limited Access :
- Description : Access to elements is restricted to the front (for removal) and
rear (for addition). Direct access to other elements is not possible.
- Example : Cannot retrieve elements from the middle of the queue without
removing them.

2. Fixed Size (for Array-based Implementation) :

- Description : In array-based implementations, the size of the queue is fixed
and may need to be resized if the capacity is exceeded.
- Example : Queue overflow can occur if the queue exceeds its allocated size.

3. Complexity in Circular Queues :

- Description : Implementing circular queues requires managing wrap-around
behavior, which can add complexity.
- Example : Handling the transition from the end of the array back to the
beginning.

---

### Use Cases of Queues

1. Task Scheduling :
- Description : Queues are used to manage tasks or processes that need to be
executed in the order they arrive.
- Example : Operating systems use queues to schedule processes and manage
CPU execution.

2. Buffering :
- Description : Queues are used to buffer data between producers and
consumers, allowing smooth data transfer.
- Example : Print spooling where print jobs are queued and processed in order.

3. Breadth-First Search (BFS) :

- Description : Queues are used in BFS algorithms to explore nodes level by
level.
- Example : Finding the shortest path in unweighted graphs and navigating
maze-like structures.

4. Event Handling :
- Description : Queues are used to manage events and handle them in the order
they occur.
- Example : Event-driven programming and handling user inputs in GUI
applications.

5. Message Queuing :
- Description : Used in distributed systems to handle messages between
different components or services.
- Example : Messaging systems like RabbitMQ and Apache Kafka.

---
### Conclusion

Queues are fundamental data structures that support FIFO operations, making
them ideal for tasks involving sequential processing and buffering. Their simplicity
and efficiency in managing ordered data make them widely used in various
applications, from task scheduling to real-time event handling. Understanding
queues and their operations is essential for implementing and solving problems
that require orderly data processing and management.

### Stack and Queue Implementations

1. Stack Implementation Using Arrays

Stack : A stack follows the Last In, First Out (LIFO) principle. You can implement a
stack using an array with the following operations:

- Push : Add an element to the top of the stack.

- Pop : Remove and return the element from the top of the stack.
- Peek (Top) : View the top element without removing it.
- IsEmpty : Check if the stack is empty.

C++ Implementation:

```cpp
#include <iostream>
#define MAX 100 // Maximum size of the stack

class Stack {
private:
int top;
int arr[MAX];

public:
Stack() : top(-1) {} // Constructor initializes top to -1

void push(int value) {

if (top >= (MAX - 1)) {
std::cout << "Stack Overflow\n";
return;
}
arr[++top] = value; // Increment top and add value
}

int pop() {
if (top < 0) {
std::cout << "Stack Underflow\n";
return -1;
}
return arr[top--]; // Return top element and decrement top
}

int peek() {
if (top < 0) {
std::cout << "Stack is Empty\n";
return -1;
}
return arr[top]; // Return top element
}

bool isEmpty() {
return top < 0; // Check if top is less than 0
}
};

int main() {
Stack s;
s.push(10);
s.push(20);
std::cout << "Top element: " << s.peek() << std::endl; // Outputs 20
std::cout << "Popped element: " << s.pop() << std::endl; // Outputs 20
std::cout << "Top element: " << s.peek() << std::endl; // Outputs 10
return 0;
}
```

Java Implementation:

```java
public class Stack {
private static final int MAX = 100; // Maximum size of the stack
private int top;
private int[] arr;

public Stack() {
arr = new int[MAX];
top = -1; // Constructor initializes top to -1
}

public void push(int value) {

if (top >= (MAX - 1)) {
System.out.println("Stack Overflow");
return;
}
arr[++top] = value; // Increment top and add value
}

public int pop() {

if (top < 0) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top--]; // Return top element and decrement top
}

public int peek() {

if (top < 0) {
System.out.println("Stack is Empty");
return -1;
}
return arr[top]; // Return top element
}

public boolean isEmpty() {

return top < 0; // Check if top is less than 0
}

public static void main(String[] args) {

Stack s = new Stack();
s.push(10);
s.push(20);
System.out.println("Top element: " + s.peek()); // Outputs 20
System.out.println("Popped element: " + s.pop()); // Outputs 20
System.out.println("Top element: " + s.peek()); // Outputs 10
}
}
```

2. Queue Implementation Using Arrays

Queue : A queue follows the First In, First Out (FIFO) principle. You can
implement a queue using an array with the following operations:

- Enqueue : Add an element to the rear of the queue.

- Dequeue : Remove and return the element from the front of the queue.
- Peek (Front) : View the front element without removing it.
- IsEmpty : Check if the queue is empty.

C++ Implementation:

```cpp
#include <iostream>
#define MAX 100 // Maximum size of the queue

class Queue {
private:
int front, rear, size;
int arr[MAX];

public:
Queue() : front(0), rear(-1), size(0) {} // Constructor initializes front, rear, and
size

void enqueue(int value) {

if (size >= MAX) {
std::cout << "Queue Overflow\n";
return;
}
rear = (rear + 1) % MAX; // Increment rear in a circular manner
arr[rear] = value;
size++;
}

int dequeue() {
if (size <= 0) {
std::cout << "Queue Underflow\n";
return -1;
}
int value = arr[front];
front = (front + 1) % MAX; // Increment front in a circular manner
size--;
return value;
}

int peek() {
if (size <= 0) {
std::cout << "Queue is Empty\n";
return -1;
}
return arr[front]; // Return front element
}

bool isEmpty() {
return size <= 0; // Check if size is less than or equal to 0
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
std::cout << "Front element: " << q.peek() << std::endl; // Outputs 10
std::cout << "Dequeued element: " << q.dequeue() << std::endl; // Outputs 10
std::cout << "Front element: " << q.peek() << std::endl; // Outputs 20
return 0;
}
```

Java Implementation:

```java
public class Queue {
private static final int MAX = 100; // Maximum size of the queue
private int front, rear, size;
private int[] arr;

public Queue() {
arr = new int[MAX];
front = 0;
rear = -1;
size = 0; // Constructor initializes front, rear, and size
}
public void enqueue(int value) {
if (size >= MAX) {
System.out.println("Queue Overflow");
return;
}
rear = (rear + 1) % MAX; // Increment rear in a circular manner
arr[rear] = value;
size++;
}

public int dequeue() {

if (size <= 0) {
System.out.println("Queue Underflow");
return -1;
}
int value = arr[front];
front = (front + 1) % MAX; // Increment front in a circular manner
size--;
return value;
}

public int peek() {

if (size <= 0) {
System.out.println("Queue is Empty");
return -1;
}
return arr[front]; // Return front element
}

public boolean isEmpty() {

return size <= 0; // Check if size is less than or equal to 0
}

public static void main(String[] args) {

Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
System.out.println("Front element: " + q.peek()); // Outputs 10
System.out.println("Dequeued element: " + q.dequeue()); // Outputs 10
System.out.println("Front element: " + q.peek()); // Outputs 20
}
}
```

Note: For both stacks and queues, array-based implementations can be simple
but may face limitations such as fixed size and potential overflow. For more
dynamic behavior, linked list-based implementations or other data structures
might be more suitable.

### Tree Data Structure

Definition : A tree is a hierarchical data structure consisting of nodes, where each
node has a value and can have zero or more child nodes. It is used to represent
data with a hierarchical relationship, such as organizational structures or file
systems.

Key Terms :
- Root : The topmost node of the tree.
- Node : An element of the tree that contains a value and pointers to its child
nodes.
- Edge : A connection between two nodes.
- Leaf : A node with no children.
- Subtree : A tree consisting of a node and its descendants.
- Height : The length of the longest path from a node to a leaf.

---

### Types of Trees

1. Binary Tree
- Definition : A tree in which each node has at most two children, referred to as
the left child and the right child.
- Characteristics :
- Complete Binary Tree : All levels, except possibly the last, are completely
filled. The last level is filled from left to right.
- Full Binary Tree : Every node has either 0 or 2 children.
- Perfect Binary Tree : All internal nodes have exactly two children, and all leaf
nodes are at the same level.
- Code Example (C++):

```cpp
#include <iostream>

struct Node {
int data;
Node* left;
Node* right;

Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

void inorderTraversal(Node* root) {

if (root != nullptr) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}

int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

std::cout << "Inorder Traversal: ";

inorderTraversal(root);

return 0;
}
```

- Code Example (Java):

```java
class TreeNode {
int data;
TreeNode left, right;

TreeNode(int value) {
data = value;
left = right = null;
}
}

public class BinaryTree {

public void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
}

public static void main(String[] args) {

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

BinaryTree tree = new BinaryTree();

System.out.print("Inorder Traversal: ");
tree.inorderTraversal(root);
}
}
```

2. Binary Search Tree (BST)

- Definition : A binary tree in which each node follows the BST property: all left
descendants are less than the node, and all right descendants are greater than
the node.
- Characteristics :
- Inorder Traversal results in sorted order of elements.
- Efficient operations for insertion, deletion, and lookup.
- Code Example (C++):

```cpp
#include <iostream>

struct BSTNode {
int data;
BSTNode* left;
BSTNode* right;

BSTNode(int value) : data(value), left(nullptr), right(nullptr) {}

};

BSTNode* insert(BSTNode* root, int value) {

if (root == nullptr) {
return new BSTNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}

void inorderTraversal(BSTNode* root) {

if (root != nullptr) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}

int main() {
BSTNode* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

std::cout << "Inorder Traversal: ";

inorderTraversal(root);

return 0;
}
```

- Code Example (Java):

```java
class BSTNode {
int data;
BSTNode left, right;

BSTNode(int value) {
data = value;
left = right = null;
}
}

public class BinarySearchTree {

public BSTNode insert(BSTNode root, int value) {
if (root == null) {
return new BSTNode(value);
}
if (value < root.data) {
root.left = insert(root.left, value);
} else {
root.right = insert(root.right, value);
}
return root;
}

public void inorderTraversal(BSTNode root) {

if (root != null) {
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
}

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();
BSTNode root = null;
root = bst.insert(root, 50);
bst.insert(root, 30);
bst.insert(root, 70);
bst.insert(root, 20);
bst.insert(root, 40);
bst.insert(root, 60);
bst.insert(root, 80);

System.out.print("Inorder Traversal: ");

bst.inorderTraversal(root);
}
}
```

3. Balanced Tree
- Definition : A binary tree where the height of the two subtrees of any node
differs by at most one. Common examples include AVL trees and Red-Black trees.
- Characteristics :
- AVL Tree : Self-balancing binary search tree with O(log n) time complexity for
insertion, deletion, and lookup.
- Red-Black Tree : A balanced binary search tree with an additional color
property to ensure balanced height.

- Code Example (C++ - AVL Tree) :

```cpp
#include <iostream>
#include <algorithm>

struct AVLNode {
int data;
AVLNode* left;
AVLNode* right;
int height;

AVLNode(int value) : data(value), left(nullptr), right(nullptr), height(1) {}

};

int height(AVLNode* node) {

return node ? node->height : 0;
}

int balanceFactor(AVLNode* node) {

return height(node->left) - height(node->right);
}
void updateHeight(AVLNode* node) {
node->height = 1 + std::max(height(node->left), height(node->right));
}

AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
}

AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}

AVLNode* insert(AVLNode* node, int value) {

if (!node) return new AVLNode(value);
if (value < node->data)
node->left = insert(node->left, value);
else
node->right = insert(node->right, value);

updateHeight(node);

int balance = balanceFactor(node);

if (balance > 1 && value < node->left->data)
return rotateRight(node);
if (balance < -1 && value > node->right->data)
return rotateLeft(node);
if (balance > 1 && value > node->left->data) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
if (balance < -1 && value < node->right->data) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}

return node;
}

void inorderTraversal(AVLNode* root) {

if (root != nullptr) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}

int main() {
AVLNode* root = nullptr;
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 10);
root = insert(root, 5);

std::cout << "Inorder Traversal: ";

inorderTraversal(root);

return 0;

}
```

- Code Example (Java - AVL Tree) :

```java
class AVLNode {
int data;
AVLNode left, right;
int height;

AVLNode(int value) {
data = value;
left = right = null;
height = 1;
}
}

public class AVLTree {

public int height(AVLNode node) {
return node == null ? 0 : node.height;
}

public int balanceFactor(AVLNode node) {

return height(node.left) - height(node.right);
}

public void updateHeight(AVLNode node) {

node.height = 1 + Math.max(height(node.left), height(node.right));
}

public AVLNode rotateRight(AVLNode y) {

AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
updateHeight(y);
updateHeight(x);
return x;
}

public AVLNode rotateLeft(AVLNode x) {

AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}

public AVLNode insert(AVLNode node, int value) {

if (node == null) return new AVLNode(value);
if (value < node.data)
node.left = insert(node.left, value);
else
node.right = insert(node.right, value);
updateHeight(node);

int balance = balanceFactor(node);

if (balance > 1 && value < node.left.data)
return rotateRight(node);
if (balance < -1 && value > node.right.data)
return rotateLeft(node);
if (balance > 1 && value > node.left.data) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && value < node.right.data) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}

return node;
}

public void inorderTraversal(AVLNode root) {

if (root != null) {
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
AVLNode root = null;
root = tree.insert(root, 30);
root = tree.insert(root, 20);
root = tree.insert(root, 10);
root = tree.insert(root, 5);

System.out.print("Inorder Traversal: ");

tree.inorderTraversal(root);
}
}
```

4. Heap
- Definition : A special tree-based structure that satisfies the heap property. In a
max-heap, each parent node is greater than or equal to its child nodes. In a min-
heap, each parent node is less than or equal to its child nodes.
- Characteristics :
- Max-Heap : The largest element is at the root.
- Min-Heap : The smallest element is at the root.

- Code Example (C++ - Max-Heap) :

```cpp
#include <iostream>
#include <vector>

class MaxHeap {
private:
std::vector<int> heap;

void heapify(int index) {

int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;

if (left < heap.size() && heap[left] > heap[largest])

largest = left;

if (right < heap.size() && heap[right] > heap[largest])

largest = right;

if (largest != index) {
std::swap(heap[index], heap[largest]);
heapify(largest);
}
}

public:
void insert(int value) {
heap.push_back(value);
int index = heap.size() - 1;
while (index != 0 && heap[(index - 1) / 2] < heap[index]) {
std::swap(heap[index], heap[(index - 1) / 2]);
index = (index - 1) / 2;
}
}

int extractMax() {
if (heap.empty()) return -1;
if (heap.size() == 1) {
int root = heap[0];
heap.pop_back();
return root;
}

int root = heap[0];

heap[0] = heap.back();
heap.pop_back();
heapify(0);

return root;
}

void printHeap() {
for (int value : heap)
std::cout << value << " ";
std::cout << std::endl;
}
};

int main() {
MaxHeap mh;
mh.insert(10);
mh.insert(20);
mh.insert(15);
mh.insert(30);
mh.insert(40);

std::cout << "Heap: ";

mh.printHeap();

std::cout << "Extracted max: " << mh.extractMax() << std::endl;

std::cout << "Heap after extraction: ";

mh.printHeap();

return 0;
}
```

- Code Example (Java - Max-Heap) :

```java
import java.util.ArrayList;
import java.util.Collections;

public class MaxHeap {

private ArrayList<Integer> heap;

public MaxHeap() {
heap = new ArrayList<>();
}

public void insert(int value) {

heap.add(value);
int index = heap.size() - 1;
while (index != 0 && heap.get((index - 1) / 2) < heap.get(index)) {
Collections.swap(heap, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}

public int extractMax() {

if (heap.isEmpty()) return -1;
if (heap.size() == 1) {
return heap.remove(0);
}
int root = heap.get(0);
heap.set(0, heap.remove(heap.size() - 1));
heapify(0);

return root;
}

private void heapify(int index) {

int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;

if (left < heap.size() && heap.get(left) > heap.get(largest))

largest = left;

if (right < heap.size() && heap.get(right) > heap.get(largest))

largest = right;

if (largest != index) {
Collections.swap(heap, index, largest);
heapify(largest);
}
}

public void printHeap() {

for (int value : heap)
System.out.print(value + " ");
System.out.println();
}

public static void main(String[] args) {

MaxHeap mh = new MaxHeap();
mh.insert(10);
mh.insert(20);
mh.insert(15);
mh.insert(30);
mh.insert(40);

System.out.print("Heap: ");
mh.printHeap();

System.out.println("Extracted max: " + mh.extractMax());

System.out.print("Heap after extraction: ");

mh.printHeap();
}
}
```

5. Trie
- Definition : A tree-like data structure used for efficient retrieval of keys in a
dataset of strings, such as dictionaries or word lists.
- Characteristics :
- Each node represents a common prefix of some strings.
- The root represents an empty string.
- Each edge represents a single character.

- Code Example (C++):

```cpp
#include <iostream>
#include <unordered_map>

class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
bool isEndOfWord;

TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
TrieNode* root;

public:
Trie() {
root = new TrieNode();
}
void insert(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.find(ch) == node->children.end()) {
node->children[ch] = new TrieNode();
}
node = node->children[ch];
}
node->isEndOfWord = true;
}

bool search(const std::string& word) {

TrieNode* node = root;
for (char ch : word) {
if (node->children.find(ch) == node->children.end()) {
return false;
}
node = node->children[ch];
}
return node->isEndOfWord;
}
};

int main() {
Trie trie;
trie.insert("hello");
trie.insert("world");

std::cout << "Search hello: " << (trie.search("hello") ? "Found" : "Not Found")
<< std::endl;
std::cout << "Search world: " << (trie.search("world") ? "Found

" : "Not Found") << std::endl;

std::cout << "Search test: " << (trie.search("test") ? "Found" : "Not Found") <<
std::endl;

return 0;
}
```

- Code Example (Java):

```java
import java.util.HashMap;

class TrieNode {
HashMap<Character, TrieNode> children;
boolean isEndOfWord;

TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}

public class Trie {

private TrieNode root;

public Trie() {
root = new TrieNode();
}

public void insert(String word) {

TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) {
node.children.put(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.isEndOfWord = true;
}

public boolean search(String word) {

TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) {
return false;
}
node = node.children.get(ch);
}
return node.isEndOfWord;
}

public static void main(String[] args) {

Trie trie = new Trie();
trie.insert("hello");
trie.insert("world");

System.out.println("Search hello: " + (trie.search("hello") ? "Found" : "Not

Found"));
System.out.println("Search world: " + (trie.search("world") ? "Found" : "Not
Found"));
System.out.println("Search test: " + (trie.search("test") ? "Found" : "Not
Found"));
}
}
```

---

Use Cases of Trees :

- Binary Trees : Used in binary search operations, expression parsing, and
implementing priority queues.
- Binary Search Trees : Efficient for dynamic data retrieval, such as database
indexing and associative arrays.
- AVL Trees and Red-Black Trees : Used in databases and file systems for
balanced data retrieval.
- Heaps : Utilized in priority queues and heap sort algorithms.
- Tries : Efficient for dictionary implementations, autocomplete systems, and
spell checkers.

### Binary Tree

Definition :
A binary tree is a hierarchical data structure in which each node has at most two
children, referred to as the left child and the right child. It is a special case of a
tree data structure with the following properties.

---

Properties of a Binary Tree :

1. Node : Each element in the tree is called a node.

2. Root : The top node of the tree is called the root.
3. Children : Nodes that are directly connected to another node when moving
away from the root are called children.
4. Parent : The node directly connected to another node when moving towards
the root is called the parent.
5. Leaf : A node with no children is called a leaf or terminal node.
6. Subtree : A node's subtree consists of that node and all its descendants.
7. Height : The height of a node is the number of edges on the longest path from
that node to a leaf.
8. Depth : The depth of a node is the number of edges from the root to that node.
9. Level : The level of a node is the number of edges from the root to that node
plus one.
10. Full Binary Tree : Every node has either 0 or 2 children.
11. Complete Binary Tree : All levels are fully filled except possibly the last level,
which is filled from left to right.
12. Perfect Binary Tree : All levels are fully filled, and all leaves are at the same
level.
13. Balanced Binary Tree : The height of the left and right subtrees of any node
differ by at most one.

---

Min-Max Height Computation of Binary Tree :

1. Minimum Height :
- Definition : The minimum height of a binary tree is computed for the most
compact (full) binary tree where nodes are filled from left to right.
- Formula : For a complete binary tree with \( n \) nodes, the minimum height \( h
\) can be computed as:
\[
h = \left\lfloor \log_2(n+1) \right\rfloor
\]
- Example : For a binary tree with 7 nodes:
\[
h = \left\lfloor \log_2(7+1) \right\rfloor = \left\lfloor \log_2(8) \right\rfloor = 3
\]

2. Maximum Height :
- Definition : The maximum height of a binary tree occurs in a degenerate (or
pathological) tree where each node has only one child, resembling a linked list.
- Formula : For a binary tree with \( n \) nodes, the maximum height \( h \) is:
\[
h=n-1
\]
- Example : For a binary tree with 7 nodes (in a degenerate form):
\[
h=7-1=6
\]

---

Code Examples :

1. Binary Tree Implementation (C++) :

```cpp
#include <iostream>
#include <algorithm> // For std::max

class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinaryTree {
private:
TreeNode* root;

int height(TreeNode* node) {

if (node == nullptr) return -1; // Height of empty tree is -1
return 1 + std::max(height(node->left), height(node->right));
}

public:
BinaryTree() : root(nullptr) {}

void insert(int value) {

root = insertRec(root, value);
}

TreeNode* insertRec(TreeNode* node, int value) {

if (node == nullptr) {
node = new TreeNode(value);
return node;
}
if (value < node->data) {
node->left = insertRec(node->left, value);
} else {
node->right = insertRec(node->right, value);
}
return node;
}

int getHeight() {
return height(root);
}
};

int main() {
BinaryTree tree;
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(20);

std::cout << "Height of the tree: " << tree.getHeight() << std::endl;

return 0;
}
```
2. Binary Tree Implementation (Java) :

```java
import java.util.*;

class TreeNode {
int data;
TreeNode left, right;

TreeNode(int value) {
data = value;
left = right = null;
}
}

public class BinaryTree {

TreeNode root;

BinaryTree() {
root = null;
}

void insert(int value) {

root = insertRec(root, value);
}
TreeNode insertRec(TreeNode node, int value) {
if (node == null) {
node = new TreeNode(value);
return node;
}
if (value < node.data) {
node.left = insertRec(node.left, value);
} else {
node.right = insertRec(node.right, value);
}
return node;
}

int height(TreeNode node) {

if (node == null) return -1; // Height of empty tree is -1
return 1 + Math.max(height(node.left), height(node.right));
}

int getHeight() {
return height(root);
}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(20);

System.out.println("Height of the tree: " + tree.getHeight());

}
}
```

---

Real-World Use Cases :

- Binary Trees : Used in binary search operations, decision-making processes,
and hierarchical data representations.
- Min-Max Height Computation : Important for balancing trees in applications
such as databases and file systems to ensure efficient data retrieval and
management.

### Binary Search Tree (BST)

Definition :
A Binary Search Tree (BST) is a type of binary tree where each node has at most
two children, and the nodes are arranged in such a way that for each node:
- The left child’s key is less than the parent’s key.
- The right child’s key is greater than the parent’s key.
This property makes BSTs useful for searching, insertion, and deletion operations
with average time complexities of O(log n) for balanced trees.

---

Properties of a Binary Search Tree :

1. Node : Each node contains a key, a left child, and a right child.
2. Root : The topmost node of the tree is the root.
3. Left Subtree : All nodes in the left subtree of a node have keys less than the
node's key.
4. Right Subtree : All nodes in the right subtree of a node have keys greater than
the node's key.
5. Inorder Traversal : Inorder traversal of a BST yields keys in non-decreasing
order.

---

Min-Max Height Computation of a BST :

1. Minimum Height :
- Definition : The minimum height of a BST occurs in a perfectly balanced BST
where the number of nodes is optimal for the height.
- Formula : For a balanced BST with \( n \) nodes, the minimum height \( h \) is:
\[
h = \left\lfloor \log_2(n+1) \right\rfloor
\]
- Example : For a BST with 7 nodes:
\[
h = \left\lfloor \log_2(7+1) \right\rfloor = \left\lfloor \log_2(8) \right\rfloor = 3
\]

2. Maximum Height :
- Definition : The maximum height of a BST occurs in a degenerate (or
pathological) tree where each node has only one child, making it similar to a
linked list.
- Formula : For a BST with \( n \) nodes, the maximum height \( h \) is:
\[
h=n-1
\]
- Example : For a BST with 7 nodes (in a degenerate form):
\[
h=7-1=6
\]

---

Code Examples :

1. BST Implementation (C++) :

```cpp
#include <iostream>
#include <algorithm> // For std::max
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;

TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}

};

class BST {
private:
TreeNode* root;

TreeNode* insertRec(TreeNode* node, int value) {

if (node == nullptr) {
node = new TreeNode(value);
return node;
}
if (value < node->data) {
node->left = insertRec(node->left, value);
} else {
node->right = insertRec(node->right, value);
}
return node;
}
TreeNode* searchRec(TreeNode* node, int value) {
if (node == nullptr || node->data == value) return node;
if (value < node->data) return searchRec(node->left, value);
return searchRec(node->right, value);
}

int height(TreeNode* node) {

if (node == nullptr) return -1;
return 1 + std::max(height(node->left), height(node->right));
}

public:
BST() : root(nullptr) {}

void insert(int value) {

root = insertRec(root, value);
}

bool search(int value) {

return searchRec(root, value) != nullptr;
}

int getHeight() {
return height(root);
}
};

int main() {
BST tree;
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(20);

std::cout << "Height of the BST: " << tree.getHeight() << std::endl;
std::cout << "Search 15: " << (tree.search(15) ? "Found" : "Not Found") <<
std::endl;
std::cout << "Search 8: " << (tree.search(8) ? "Found" : "Not Found") <<
std::endl;

return 0;
}
```

2. BST Implementation (Java) :

```java
class TreeNode {
int data;
TreeNode left, right;

TreeNode(int value) {
data = value;
left = right = null;
}
}

public class BST {

TreeNode root;

BST() {
root = null;
}

void insert(int value) {

root = insertRec(root, value);
}

TreeNode insertRec(TreeNode node, int value) {

if (node == null) {
node = new TreeNode(value);
return node;
}
if (value < node.data) {
node.left = insertRec(node.left, value);
} else {
node.right = insertRec(node.right, value);
}
return node;
}

boolean search(int value) {

return searchRec(root, value) != null;
}

TreeNode searchRec(TreeNode node, int value) {

if (node == null || node.data == value) return node;
if (value < node.data) return searchRec(node.left, value);
return searchRec(node.right, value);
}

int height(TreeNode node) {

if (node == null) return -1;
return 1 + Math.max(height(node.left), height(node.right));
}

int getHeight() {
return height(root);
}

public static void main(String[] args) {

BST tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(20);

System.out.println("Height of the BST: " + tree.getHeight());

System.out.println("Search 15: " + (tree.search(15) ? "Found" : "Not
Found"));
System.out.println("Search 8: " + (tree.search(8) ? "Found" : "Not Found"));
}
}
```

---

Real-World Use Cases :

- BSTs : Used in applications requiring dynamic set operations such as search,
insert, and delete. Examples include database indexing, in-memory sorting, and
implementing associative arrays.

Feel free to ask if you need further elaboration or additional topics!

### AVL Tree

Definition :
An AVL tree is a self-balancing binary search tree where the difference in height
between the left and right subtrees of any node (called the balance factor) is at
most one. Named after its inventors Adelson-Velsky and Landis, the AVL tree
ensures that the tree remains balanced, which provides logarithmic time
complexity for search, insert, and delete operations.

---

Properties of AVL Tree :

1. Balance Factor : For every node in the tree, the height difference between the
left and right subtrees (balance factor) is -1, 0, or 1.
2. Height : The height of an AVL tree with \( n \) nodes is \( O(\log n) \), ensuring
efficient operations.
3. Rotations : AVL trees use rotations to maintain balance after insertions and
deletions. There are four types of rotations:
- Right Rotation (RR)
- Left Rotation (LL)
- Left-Right Rotation (LR)
- Right-Left Rotation (RL)

---

Rotations :
1. Right Rotation (RR) :
- Scenario : Used when a node’s left subtree is taller than its right subtree.
- Example :
```
30
/
20
/
10
```
After right rotation:
```
20
/\
10 30
```

2. Left Rotation (LL) :

- Scenario : Used when a node’s right subtree is taller than its left subtree.
- Example :
```
10
\
20
\
30
```
After left rotation:
```
20
/\
10 30
```

3. Left-Right Rotation (LR) :

- Scenario : Used when the left child of the right subtree is taller.
- Example :
```
30
/
10
\
20
```
After left-right rotation:
```
20
/\
10 30
```

4. Right-Left Rotation (RL) :

- Scenario : Used when the right child of the left subtree is taller.
- Example :
```
10
\
30
/
20
```
After right-left rotation:
```
20
/\
10 30
```

---

Code Examples :

1. AVL Tree Implementation (C++) :

```cpp
#include <iostream>
#include <algorithm>
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
int height;

TreeNode(int value) : data(value), left(nullptr), right(nullptr), height(1) {}

};

class AVLTree {
private:
TreeNode* root;

int height(TreeNode* node) {

return node ? node->height : 0;
}

int balanceFactor(TreeNode* node) {

return node ? height(node->left) - height(node->right) : 0;
}

TreeNode* rightRotate(TreeNode* y) {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = 1 + std::max(height(y->left), height(y->right));
x->height = 1 + std::max(height(x->left), height(x->right));
return x;
}

TreeNode* leftRotate(TreeNode* x) {
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = 1 + std::max(height(x->left), height(x->right));
y->height = 1 + std::max(height(y->left), height(y->right));
return y;
}

TreeNode* insertRec(TreeNode* node, int value) {

if (node == nullptr) return new TreeNode(value);
if (value < node->data) node->left = insertRec(node->left, value);
else if (value > node->data) node->right = insertRec(node->right, value);
else return node;

node->height = 1 + std::max(height(node->left), height(node->right));

int balance = balanceFactor(node);

if (balance > 1 && value < node->left->data) return rightRotate(node);
if (balance < -1 && value > node->right->data) return leftRotate(node);
if (balance > 1 && value > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && value < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}

public:
AVLTree() : root(nullptr) {}

void insert(int value) {

root = insertRec(root, value);
}

void inOrder(TreeNode* node) {

if (node) {
inOrder(node->left);
std::cout << node->data << " ";
inOrder(node->right);
}
}
void printInOrder() {
inOrder(root);
std::cout << std::endl;
}
};

int main() {
AVLTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);

std::cout << "InOrder Traversal: ";

tree.printInOrder();

return 0;
}
```

2. AVL Tree Implementation (Java) :

```java
class TreeNode {
int data;
TreeNode left, right;
int height;

TreeNode(int value) {
data = value;
left = right = null;
height = 1;
}
}

public class AVLTree {

TreeNode root;

int height(TreeNode node) {

return node != null ? node.height : 0;
}

int balanceFactor(TreeNode node) {

return node != null ? height(node.left) - height(node.right) : 0;
}

TreeNode rightRotate(TreeNode y) {
TreeNode x = y.left;
TreeNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = 1 + Math.max(height(y.left), height(y.right));
x.height = 1 + Math.max(height(x.left), height(x.right));
return x;
}

TreeNode leftRotate(TreeNode x) {
TreeNode y = x.right;
TreeNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}

TreeNode insertRec(TreeNode node, int value) {

if (node == null) return new TreeNode(value);
if (value < node.data) node.left = insertRec(node.left, value);
else if (value > node.data) node.right = insertRec(node.right, value);
else return node;

node.height = 1 + Math.max(height(node.left), height(node.right));

int balance = balanceFactor(node);

if (balance > 1 && value < node.left.data) return rightRotate(node);
if (balance < -1 && value > node.right.data) return leftRotate(node);
if (balance > 1 && value > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && value < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}

void insert(int value) {

root = insertRec(root, value);
}

void inOrder(TreeNode node) {

if (node != null) {
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
}

void printInOrder() {
inOrder(root);
System.out.println();
}

public static void main(String[] args) {

AVLTree tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);

System.out.println("InOrder Traversal: ");

tree.printInOrder();
}
}
```

---

Real-World Use Cases :

- AVL Trees : Used in applications requiring frequent insertions and deletions
while maintaining balanced search times, such as databases, file systems, and
memory management systems.

Feel free to ask if you have more questions or need additional topics covered!