# Palindrome Partitioning Problem

**Problem Statement:**

Given a string `s`, the task is to partition the string into all possible palindrome substrings. We need to find and return all possible valid partitions where each substring is a palindrome.

## Approach:

### 1. **ispalindrome Function:**

The `ispalindrome` function checks whether a given substring of string `s` is a palindrome.

#### Parameters:
- `s`: The input string.
- `start`: The starting index of the substring.
- `end`: The ending index of the substring.

#### Implementation:
- This function uses a two-pointer approach to compare characters from both ends of the substring.
- If any characters don’t match, it returns `false`, indicating the substring is not a palindrome.
- If all characters match, it returns `true` and prints the palindrome substring.

### 2. **calculate Function:**

The `calculate` function recursively generates all valid partitions of the input string `s`.

#### Parameters:
- `index`: The current index in the string.
- `t`: A vector of vectors that stores the valid palindrome partitions.
- `s`: The input string.
- `path`: A vector that stores the current partition path.

#### Implementation:
- The function works recursively and explores all possible substrings starting from the `index`.
- If the substring from `index` to `i` is a palindrome, we add it to the `path`.
- The function then recursively calls itself with the updated `index` and the current `path`.
- If the `index` reaches the end of the string, we’ve found a valid partition, and we add it to the result (`t`).
- Backtracking is performed by removing the last added palindrome from the `path`.

### 3. **partition Function:**

This is the main function that initializes the process of palindrome partitioning.

#### Parameter:
- `s`: The input string.

#### Implementation:
- The function initializes an empty vector of vectors (`t`) to store the valid palindrome partitions.
- It also initializes an empty vector (`path`) to store the current partition path.
- The `calculate` function is called with initial parameters to start the recursive partition generation process.
- Finally, the function returns the vector `t` containing all valid palindrome partitions.

---

## Test Cases

### Test Case 1: Basic Case with Single Palindrome

**Input:**  
`s = "aab"`

**Output:**  
`[["a", "a", "b"], ["aa", "b"]]`

**Explanation:**  
The string `"aab"` can be partitioned in two valid ways:
1. `"a"`, `"a"`, `"b"`
2. `"aa"`, `"b"`

---

### Test Case 2: String with All Palindromes

**Input:**  
`s = "a"`

**Output:**  
`[["a"]]`

**Explanation:**  
The string `"a"` is already a palindrome, so the only partition is itself.

---

### Test Case 3: String with Multiple Palindromes

**Input:**  
`s = "racecar"`

**Output:**  
`[["r", "a", "c", "e", "c", "a", "r"], ["racecar"]]`

**Explanation:**  
The string `"racecar"` can be partitioned in two valid ways:
1. `"r"`, `"a"`, `"c"`, `"e"`, `"c"`, `"a"`, `"r"`
2. `"racecar"` (the whole string is a palindrome)

---

### Test Case 4: No Palindrome Substring

**Input:**  
`s = "abc"`

**Output:**  
`[["a", "b", "c"]]`

**Explanation:**  
Since no two characters form a valid palindrome substring except for the single characters, the only valid partition is each character individually.

---

### Test Case 5: Larger Input with Palindromes

**Input:**  
`s = "aabb"`

**Output:**  
`[["a", "a", "b", "b"], ["aa", "b", "b"], ["a", "a", "bb"]]`

**Explanation:**  
The string `"aabb"` can be partitioned into the following valid palindrome partitions:
1. `"a"`, `"a"`, `"b"`, `"b"`
2. `"aa"`, `"b"`, `"b"`
3. `"a"`, `"a"`, `"bb"`

---  


Saurabh Patil

# Kadane's Algorithm  

**Objective:** Find the contiguous subarray within a given array that has the maximum sum using Kadane's algorithm.  

---

## Problem Description  

Kadane's algorithm is a **dynamic programming approach** that efficiently solves this problem in **O(n)** time, where *n* is the number of elements in the array.

---

## Steps to Solve the Problem  

### 1. **Initialization:**  
- Maintain two variables:  
  - **`max_ending_here`**: Stores the maximum sum of a contiguous subarray ending at the current index.  
  - **`max_so_far`**: Stores the overall maximum sum of a contiguous subarray found so far.  
- Both variables are initialized to the first element of the array.

---

### 2. **Iteration:**  
- Loop through the array starting from the **second element** (index 1).  
- At each index:  
  1. **Check Current Element:**  
     - If the current element (`arr[i]`) is greater than `max_ending_here + arr[i]`, start a new subarray from the current element:  
       `max_ending_here = arr[i]`.  
     - Otherwise, extend the current subarray:  
       `max_ending_here = max_ending_here + arr[i]`.  
  2. **Update Overall Maximum:**  
     - Compare `max_ending_here` with `max_so_far`.  
     - If `max_ending_here` is larger, update `max_so_far`:  
       `max_so_far = max(max_so_far, max_ending_here)`.

---

### 3. **Result:**  
- After iterating through the entire array, `max_so_far` contains the **maximum sum of a contiguous subarray**.

---

## Example  

**Input Array:**  
`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`  

---

### Iteration Breakdown:  

- **Index 0**: Element `-2`  
  - `max_ending_here = -2`  
  - `max_so_far = -2`
- **Index 1**: Element `1`  
  - `max_ending_here = 1`  
  - `max_so_far = 1`
- **Index 2**: Element `-3`  
  - `max_ending_here = -2`  
  - `max_so_far = 1`
- **Index 3**: Element `4`  
  - `max_ending_here = 4`  
  - `max_so_far = 4`
- **Index 4**: Element `-1`  
  - `max_ending_here = 3`  
  - `max_so_far = 4`
- **Index 5**: Element `2`  
  - `max_ending_here = 5`  
  - `max_so_far = 5`
- **Index 6**: Element `1`  
  - `max_ending_here = 6`  
  - `max_so_far = 6`
- **Index 7**: Element `-5`  
  - `max_ending_here = 1`  
  - `max_so_far = 6`
- **Index 8**: Element `4`  
  - `max_ending_here = 5`  
  - `max_so_far = 6`

---

### Final Result:  
**Maximum Sum of a Contiguous Subarray:** `6`  

---

## Key Insights  

- Kadane's algorithm uses a simple, iterative approach to track the maximum sum, making it efficient and elegant.  
- It dynamically adjusts whether to start a new subarray or continue the current one, based on which yields a higher sum.


# Topic: Factorials - A Breakdown and Recursive Approach  
**Difficulty:** Easy to Moderate  
**Topics:** Recursion, Iterative Algorithms, Mathematics  
**Applications:** Used in combinatorics, probability, and programming challenges.

---

## Concept of Factorials  
Imagine you have a set of building blocks, and you want to know how many unique structures you can create by stacking them in every possible arrangement. This is the idea behind factorials in mathematics.

### **Definition**  
The factorial of a number `n`, written as `n!` (n factorial), represents the total number of ways you can arrange a set of `n` distinct objects.

### **Example**  
For `n = 3` (3 blocks):  
$$
3! = 3 \times 2 \times 1 = 6 \text{ unique arrangements.}
$$
---

## Recursive Approach to Factorials  

### **What is Recursion?**  
Recursion involves solving a problem by breaking it down into smaller, similar subproblems. A **recursive function** calls itself within its body but with a smaller input until it reaches a **base case** (a condition where the function stops calling itself).

### **Factorial Using Recursion**  
To calculate `n!` using recursion:  
1. Multiply `n` by the factorial of `n-1`.  
2. Continue this process until `n` reaches the **base case**, where `n = 1` or `n = 0`.  

For these cases:  
$$
0! = 1 \quad \text{and} \quad 1! = 1.
$$

### **Recursive Formula**  
$$
n! = n \times (n-1)!
$$

---

## Example Walkthrough  
### Find `5!` Recursively:
1. `5! = 5 × 4!`  
2. `4! = 4 × 3!`  
3. `3! = 3 × 2!`  
4. `2! = 2 × 1!`  
5. `1! = 1` (Base case reached)  

**Result:**  
$$
5! = 5 \times 4 \times 3 \times 2 \times 1 = 120
$$

---


## Test Cases  

### Test Case 1: Small Number  
**Input:**  
`n = 5`  

**Execution:**  
`factorial_recursive(5)`  

**Output:**  
`120`  

---

### Test Case 2: Base Case (`n = 0`)  
**Input:**  
`n = 0`  

**Execution:**  
`factorial_recursive(0)`  

**Output:**  
`1`  

---

### Test Case 3: Base Case (`n = 1`)  
**Input:**  
`n = 1`  

**Execution:**  
`factorial_recursive(1)`  

**Output:**  
`1`  

---

### Test Case 4: Larger Number  
**Input:**  
`n = 10`  

**Execution:**  
`factorial_recursive(10)`  

**Output:**  
`3628800`  

---

# Problem: Selection Sort  
**Difficulty:** Easy  
**Topics:** Sorting Algorithms, Iterative Methods  
**Companies:** Commonly asked in technical interviews.

---

## Problem Description  
Selection sort is a sorting algorithm that iteratively selects the smallest element from the unsorted portion of the array and swaps it with the element at the beginning of the unsorted portion.

---

## How Selection Sort Works

### **1. Initialization:**  
- Start with the first element as the minimum index (`min_index`) of the unsorted portion of the array.

### **2. Outer Loop:**  
- Iterate through the array from the beginning to the second-to-last element.  
- In each iteration of this loop:  
  - Set `min_index` to the current iterator value, assuming it is the smallest within the unsorted portion.  

### **3. Inner Loop:**  
- Begin from the next element after the current iterator in the outer loop and compare it with subsequent elements:  
  - If any element is found smaller than the current `min_index`, update `min_index` to this element's index.  

### **4. Swap:**  
- After completing the inner loop, if `min_index` is different from the current iterator in the outer loop, swap the elements at `min_index` and the current iterator.  

### **5. Repeat:**  
- Continue this process until the array is sorted.  

---

## Key Idea  
Selection sort works by gradually building up a sorted portion of the array from left to right, ensuring that after each iteration of the outer loop, the left portion of the array is sorted correctly.

---

## Time Complexity  
Selection sort operates with a time complexity of **𝑂(𝑛²)**, making it less efficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

---

## Example Execution  
### Unsorted Array:  
`[64, 25, 12, 22, 11]`  

### Step-by-Step Process:
1. **First Pass:** Find the smallest element (`11`) and swap it with the first element.  
   Result: `[11, 25, 12, 22, 64]`  
2. **Second Pass:** Find the next smallest element (`12`) and swap it with the second element.  
   Result: `[11, 12, 25, 22, 64]`  
3. **Third Pass:** Find the next smallest element (`22`) and swap it with the third element.  
   Result: `[11, 12, 22, 25, 64]`  
4. **Fourth Pass:** The array is already sorted.  

### Final Sorted Array:  
`[11, 12, 22, 25, 64]`

---

## Why Use Selection Sort?  
- **Advantages:**  
  - Simple and easy to implement.  
  - Works well for small datasets or arrays that are nearly sorted.  

- **Disadvantages:**  
  - Inefficient for large datasets due to its quadratic time complexity.  
  - Not suitable for performance-critical applications.  

---

## Practical Tip  
Use selection sort for educational purposes or small datasets. For larger datasets, consider more efficient algorithms like **quicksort** or **mergesort**.


# Problem: Bubble Sort  
**Difficulty:** Easy  
**Topics:** Sorting Algorithms, Iterative Methods  
**Companies:** Commonly asked in technical interviews.

---

## Problem Description  
Bubble sort is a sorting algorithm that repeatedly compares adjacent elements in an array and swaps them if they are in the wrong order. This process continues until the array is completely sorted.

---

## How Bubble Sort Works  

### **1. Outer Loop:**  
- The outer loop iterates from the beginning to the end of the array.  
- With each iteration, the algorithm focuses on sorting the unsorted portion of the array.

### **2. Inner Loop:**  
- The inner loop compares each pair of adjacent elements in the array:  
  - If the preceding element is greater than the subsequent element, **swap** them.

### **3. Largest Element Bubbles Up:**  
- After one complete iteration of the inner loop, the largest element in the unsorted portion of the array moves to its correct position at the end.  
- This is why it’s called “Bubble Sort,” as larger elements ‘bubble up’ to the top.

### **4. Repeat:**  
- Continue the process for the remaining unsorted portion of the array until the entire array is sorted.

---

## Key Idea  
Bubble sort works by iteratively ensuring that, after each pass, the largest unsorted element moves to its correct position. After every iteration, the sorted portion of the array grows from right to left.

---

## Time Complexity  
- **Best Case (Sorted Array):** 𝑂(𝑛) with optimization (check if no swaps are needed in an iteration).  
- **Worst Case (Reversed Array):** 𝑂(𝑛²).  
- Bubble sort is inefficient for large datasets compared to more advanced algorithms like quicksort or mergesort.

---

## Example Execution  
### Unsorted Array:  
`[5, 1, 4, 2, 8]`  

### Step-by-Step Process:  
1. **First Pass:** Compare and swap adjacent elements.  
   Result: `[1, 4, 2, 5, 8]` (largest element `8` bubbles up to the end).  
2. **Second Pass:** Compare and swap adjacent elements in the remaining unsorted portion.  
   Result: `[1, 2, 4, 5, 8]` (`5` bubbles up to its correct position).  
3. **Third Pass:** No swaps are needed, indicating the array is sorted.

### Final Sorted Array:  
`[1, 2, 4, 5, 8]`

---

## Why Use Bubble Sort?  
- **Advantages:**  
  - Simple and easy to understand.  
  - Can be optimized to stop early if no swaps are needed in an iteration.

- **Disadvantages:**  
  - Inefficient for large datasets due to its quadratic time complexity.  
  - Not suitable for performance-critical applications.

---

## Practical Tip  
Bubble sort is primarily used for educational purposes to demonstrate the concept of sorting algorithms. For larger or more complex datasets, use more efficient algorithms like **quicksort** or **heapsort**.


# Problem: `Insertion Sort`

Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It is particularly efficient for small or nearly sorted datasets.

---

## How It Works

1. **Initialization**  
   Assume the first element of the array is already sorted.
2. **Iteration**  
   Starting from the second element, pick the current element (`key`) and compare it with the elements in the sorted portion (to its left).
3. **Shifting Elements**  
   Shift all elements in the sorted section that are greater than the `key` one position to the right.
4. **Insertion**  
   Insert the `key` into its correct position in the sorted section.
5. **Repeat**  
   Repeat the process for each element until the entire array is sorted.





---

## Pseudocode

```plaintext
for i = 1 to length(array) - 1:
    key = array[i]
    j = i - 1

    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1

    array[j + 1] = key
```


### Time Complexity
- Best Case: `O(n)` when the array is already sorted.
- Average/Worst Case: `O(n²)` due to the nested loop in the worst scenario.

# `Merge Sort` - A Divide and Conquer Algorithm

`Merge Sort` is an efficient, stable, and comparison-based sorting algorithm that follows the **divide and conquer** paradigm. It is particularly useful for large datasets as it has a worst-case time complexity of **O(n log n)**.

---

## How Merge Sort Works

Merge Sort follows three main steps:

1. **Divide:**  
   Recursively split the array into two halves until each sub-array contains a single element.
2. **Conquer:**  
   Since arrays of one element are inherently sorted, we now have a collection of sorted sub-arrays.
3. **Merge:**  
   Combine the sorted sub-arrays to form a single sorted array. The merging process involves comparing the smallest elements of each sub-array and arranging them in order.

---

## Example Walkthrough

Consider the array: **[8, 3, 5, 4, 2, 7, 6, 1]**

### Step 1: `Divide  `
   [8, 3, 5, 4] | [2, 7, 6, 1]


*Splitting further:*
  [8, 3] | [5, 4] and [2, 7] | [6, 1]


### Step 2: Conquer  
*Each sub-array with one element is considered sorted:*
[8] [3] [5] [4] [2] [7] [6] [1]



### Step 3: Merge  
Merge each pair of sub-arrays in sorted order:
- Merge `[8]` and `[3]` → `[3, 8]`
- Merge `[5]` and `[4]` → `[4, 5]`
- Merge `[2]` and `[7]` → `[2, 7]`
- Merge `[6]` and `[1]` → `[1, 6]`

Now merge these intermediate arrays:
- Merge `[3, 8]` and `[4, 5]` → `[3, 4, 5, 8]`
- Merge `[2, 7]` and `[1, 6]` → `[1, 2, 6, 7]`

Finally, merge `[3, 4, 5, 8]` and `[1, 2, 6, 7]` → `[1, 2, 3, 4, 5, 6, 7, 8]`

### Summary
- Merge Sort divides the array into halves, recursively sorts them, and then merges the sorted halves.
- It is highly efficient with a time complexity of `O(n log n).`


# 🚀 Quick Sort Algorithm Explained

Quick Sort is a **divide-and-conquer** algorithm that efficiently sorts an array by selecting a **pivot** element and partitioning the other elements into two groups:  
- **Smaller than the pivot**  
- **Greater than the pivot**  

This process is recursively applied to both groups until the entire array is sorted.  

---

## 📌 Steps of Quick Sort
1. **Choose a Pivot**: Pick an element from the array (commonly the last, first, or a random element).
2. **Partitioning**: Rearrange the array so that elements smaller than the pivot come before it, and elements greater come after.
3. **Recursion**: Apply Quick Sort on the left and right sub-arrays.
4. **Base Case**: When the sub-array has 0 or 1 element, it's already sorted.

---

## Quick Sort: Time Complexity & Key Takeaways

## Time Complexity Table

| **Scenario**    | **Time Complexity** | **Description**                                                       |
|-----------------|---------------------|-----------------------------------------------------------------------|
| **Best Case**   | `O(n log n)`          | Occurs when the pivot divides the array into two nearly equal parts.  |
| **Average Case**| `O(n log n) `         | Typically achieved with balanced partitions during recursion.         |
| **Worst Case**  | `O(n²)`               | Happens when the pivot is the smallest or largest element each time, leading to highly unbalanced partitions (e.g., already sorted array). |

## Key Takeaways

- **Divide and Conquer:** Quick Sort works by breaking the problem into smaller sub-problems using a pivot to partition the array.
- **Efficiency:** It generally performs very well with an average-case time complexity of O(n log n), making it suitable for large datasets.
- **Worst Case Pitfall:** Poor pivot selection (e.g., always picking the smallest or largest element) can degrade its performance to O(n²).
- **In-Place Sorting:** Quick Sort can be implemented in-place, requiring little additional memory.
- **Not Stable:** The algorithm does not maintain the relative order of equal elements.

*Quick Sort remains a popular choice due to its average-case efficiency, despite potential pitfalls with worst-case performance.*


# Linear Search Algorithm Explained

Linear search is one of the simplest search algorithms. It sequentially checks each element in a list until the desired element (the target) is found or the list ends. This approach works on both sorted and unsorted lists, making it versatile for small datasets.

---

## How Linear Search Works

1. **Iteration:** Start at the beginning of the list.
2. **Comparison:** Compare each element with the target value.
3. **Match Found:** If an element matches the target, return its index.
4. **Completion:** If no match is found by the end of the list, return an indicator (typically `-1`).

---

## Time Complexity Table

| **Scenario**    | **Time Complexity** | **Explanation**                                        |
|-----------------|---------------------|--------------------------------------------------------|
| **Best Case**   | `O(1) `               | The target is the first element in the list.         |
| **Average Case**| `O(n)`                | The target is somewhere in the middle of the list.     |
| **Worst Case**  | `O(n) `               | The target is the last element or is not present at all.|

---

## Key Takeaways

- **Simplicity:** Linear search is easy to implement and understand.
- **No Preprocessing:** It works without requiring the list to be sorted.
- **Efficiency:** While efficient for small or unsorted datasets, it is less effective for large datasets due to its O(n) time complexity.
- **Versatility:** It can be applied to any list regardless of order.

---




# 🚀 Binary Search Algorithm Explained

Binary Search is an efficient algorithm for locating a target element in a **sorted** array by repeatedly dividing the search interval in half.

---

## Steps

1. **Initialize Pointers:**  
   Set `left` to the start of the array and `right` to the end.
2. **Calculate the Middle:**  
   Compute the middle index using:  
   ```javascript
   mid = left + (right - left) / 2;
3.  **Compare and Conquer**
    - **Target Found:**  
           If the element at `mid` equals the target, return `mid` (target found).
    - **Search Right Half:**  
  If the element at `mid` is less than the target, update `left` to `mid + 1` to search the right half.
    - **Search Left Half:**  
  If the element at `mid` is greater than the target, update `right` to `mid - 1` to search the 
    left half.

4.**Repeat**

- Continue steps 2 and 3 until the target is found or `left` exceeds `right`.
- If the target is not found, return `-1`.

## Time Complexity

| **Scenario**      | **Time Complexity** | **Explanation**                                                         |
|-------------------|---------------------|-------------------------------------------------------------------------|
| **Best Case**     | O(1)                | The target is found at the middle in the first try.                     |
| **Average Case**  | O(log n)            | The search space is halved with each iteration.                         |
| **Worst Case**    | O(log n)            | Even in the worst case, the number of comparisons grows logarithmically.|


# Preorder Traversal Explained

Preorder traversal is a method used to traverse a binary tree by visiting nodes in the following order:
1. **Root Node**  
2. **Left Subtree**  
3. **Right Subtree**

This traversal is particularly useful for tasks such as copying a tree, expression evaluation, or converting the tree into another structure.

---

## Characteristics
- **Depth-First Approach:** Visits nodes deeply before backtracking.
- **Top-Down Order:** Processes the root first, then recursively visits the left and right subtrees.
- **Implementation Flexibility:** Can be implemented recursively or iteratively using a stack.

---

## How Preorder Traversal Works
1. **Visit the Root:** Start with the root node of the tree.
2. **Traverse the Left Subtree:** Recursively perform a preorder traversal on the left subtree.
3. **Traverse the Right Subtree:** Recursively perform a preorder traversal on the right subtree.

---

## Test Cases

### Test Case 1: Simple Tree
**Input Tree:**

![binary tree image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739882993/preorder1_znr1ay.png)
**Expected Output:**  
`[1, 2, 4, 5, 3]`


### Test Case 2: Tree with One Child Nodes
**Input Tree:**
![binary tree image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739883936/preorder2_sjjt2n.png)
**Expected Output:**  
`[10, 20, 30, 40]`

## Summary
Preorder traversal follows the order **Root → Left → Right**. It is a simple and effective method for visiting all the nodes in a tree, ensuring that the root is processed before its children. This method is essential in various tree-related operations and helps in understanding the hierarchical structure of data.


# Binary Tree Inorder Traversal

## What is Inorder Traversal?
Inorder traversal is a **Depth-First Traversal** method where we visit nodes in the following order:
1. **Left subtree**
2. **Root node**
3. **Right subtree**

This traversal results in nodes being visited in **sorted order** if the tree is a **Binary Search Tree (BST)**.

## Example

Consider the following binary tree:
![binary tree image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739547155/inorder_xcigll.png)

### Steps for Inorder Traversal:
1. Start from the root (1).
2. Visit the **left subtree** (2).
3. Visit the **left subtree** of (2) → (4) (no left child, so print `4`).
4. Print `2` (after visiting left subtree).
5. Visit the **right subtree** of (2) → (5) (no left child, so print `5`).
6. Print `1` (after visiting left subtree).
7. Visit the **right subtree** (3) (no left child, so print `3`).

### Inorder Traversal Output:
`4` → `2` → `5` → `1` → `3` 

## Applications of Inorder Traversal

- **Sorting elements** in a **Binary Search Tree (BST)**.
- **Expression tree evaluation** (infix notation).
- Used in **binary tree visualization tools**.



# Postorder Traversal Explained

Postorder traversal is a method of traversing a binary tree where nodes are visited in the following order:
1. **Left Subtree**
2. **Right Subtree**
3. **Root Node**

This bottom-up approach is especially useful for operations where children need to be processed before their parent, such as when deleting a tree or evaluating expression trees.

---

## How Postorder Traversal Works
1. **Traverse the Left Subtree:** Recursively visit all nodes in the left subtree.
2. **Traverse the Right Subtree:** Recursively visit all nodes in the right subtree.
3. **Visit the Root Node:** Process the root node after its subtrees have been visited.

---

## Characteristics
- **Bottom-Up Order:** Ensures that children are processed before the parent node.
- **Usage Scenarios:** Ideal for tasks such as safely deleting a tree (where you delete children before the parent) and evaluating postfix expressions.
- **Implementation:** Can be implemented either recursively or iteratively (often using two stacks).

---

## Example Test Cases

### Test Case 1: Simple Tree
**Input Tree:**
![binary tree image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739882993/preorder1_znr1ay.png)
**Expected Postorder Traversal Output:**  
`[4, 5, 2, 3, 1]`

### Test Case 2: Tree with One Child Nodes
**Input Tree:**
![binary tree image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739883936/preorder2_sjjt2n.png)
**Expected Output:**  
`[40,30,20,10]`

---

## Summary
Postorder traversal follows the **Left → Right → Root** sequence, ensuring that all descendants of a node are processed before the node itself. This order is particularly beneficial when you need to delete nodes or evaluate expressions that depend on the values of child nodes before combining them at the parent.


# Breadth-First Search (BFS) Explained

Breadth-First Search `(BFS)` is a fundamental graph traversal algorithm. It explores the graph level by level, starting from a given source node and expanding outwards to all its neighbours before moving on to the next level.

---

## Example:
**INPUT** :
 [
  [0, 1, 1, 0],
  [0, 0, 1, 0],
  [1, 0, 0, 1],
  [0, 0, 0, 1]
] , 2
![graph](https://res.cloudinary.com/dluehhlfs/image/upload/v1738943220/graph2_ksopys.png)


**OUTPUT**:
2 `->` 0 `->` 1 `->` 3

## Key Concepts
- **Graph Structure:**  
  BFS works on graphs (both `directed` and `undirected`) as well as trees.
- **Level-Order Traversal:**  
  Nodes are visited in order of their distance from the starting node (i.e., by increasing number of edges).
- **Queue Data Structure:**  
  BFS uses a FIFO (first-in, first-out) queue to keep track of nodes to visit next.

---

## How BFS Works

1. **Initialization:**  
   - Mark the starting node as visited.
   - Enqueue the starting node.
2. **Iteration:**  
   - Dequeue a node from the front of the queue.
   - Process the current node (e.g., record its value).
   - For each unvisited neighbour of the current node:
     - Mark the neighbour as visited.
     - Enqueue the neighbour.
3. **Termination:**  
   - Repeat the iteration until the queue is empty. At this point, all reachable nodes from the starting node have been visited.

---
## Time and Space Complexity

**Time Complexity:** `O(V + E) ` 
- V = number of vertices  
- E = number of edges  
- Every vertex and edge is processed once.

**Space Complexity:** O(V)  
- In the worst case, the queue holds all vertices in the graph.

---

## Applications of BFS
- **Shortest Path:**  
  BFS is ideal for finding the shortest path in unweighted graphs.
- **Level Order Traversal:**  
  In trees, BFS performs a level order traversal.
- **Connected Components:**  
  BFS can help determine the connected components in a graph.
- **Web Crawlers:**  
  Used to explore the web layer by layer starting from a seed URL.




# Depth-First Search (DFS) Algorithm

## What is DFS?
Depth-First Search `(DFS)` is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented using recursion or an explicit stack.

## DFS Algorithm:
1. Start from the root (or any arbitrary node).
2. Mark the node as visited.
3. Explore each adjacent unvisited node recursively.
4. Backtrack when no more unvisited nodes are found.

## Example:

Let's consider a simple graph:
&nbsp;  &nbsp; &nbsp;`A`
&nbsp;&nbsp;&nbsp;&nbsp;/  &nbsp;  \\
&nbsp;&nbsp;`B`  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `C `
/&nbsp;&nbsp;&nbsp;\\&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\\
`D` &nbsp;&nbsp;`E` &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`F`
### Adjacency List Representation:

```js
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B"],
  F: ["C"]
};
```

Output:

A
B
D
E
C
F

## Complexity Analysis

### Time Complexity:  
**`O(V + E)`** where **`V`** is the number of vertices and **E** is the number of edges.

### Space Complexity:  
**`O(V)`** for storing visited nodes in recursion.

## Use Cases of DFS:
- **Pathfinding algorithms** (e.g., Maze solving)  
- **Detecting cycles in graphs**  
- **Topological sorting**  
- **Connected components in a graph**  


Track and Visualize Data Structures and Algorithms in a gamified way

Escape the trap of endless tutorials—dive into each algorithm, truly grasp its inner workings, and make its logic unforgettable. Only use the DrawToCode tracking tool once you’ve mastered the algorithm; otherwise, let our visualization tools guide your understanding.

Perfect For
|

Give It a Go

Click on the Track button to visualize the Linear Search algorithm, or click View to see the problem details.

Give It a Go

Click on the Track button to visualize the Linear Search algorithm, or click View to see the problem details.

How to Visualize Data Structures and Algorithms with DrawToCode

This is how drawing on other tools looks like:

This is how tool, DrawToCode, looks like:

🌳Don't use pen and paper—use DrawToCode and help save trees!🌳

How to Track Data Structures and Algorithms with DrawToCode

Why Use DrawToCode?

Interactive Whiteboard

Track once and Remember Forever!!!💯

Trusted by Students

.css-1lhzw4j{margin:0;font-family:"Roboto","Helvetica","Arial",sans-serif;font-weight:300;font-size:3.75rem;line-height:1.2;letter-spacing:-0.00833em;}

Track and Visualize Data Structures and Algorithms in a gamified way

Escape the trap of endless tutorials—dive into each algorithm, truly grasp its inner workings, and make its logic unforgettable. Only use the DrawToCode tracking tool once you’ve mastered the algorithm; otherwise, let our visualization tools guide your understanding.

Perfect For |

Give It a Go

Click on the Track button to visualize the Linear Search algorithm, or click View to see the problem details.

Give It a Go

Click on the Track button to visualize the Linear Search algorithm, or click View to see the problem details.

How to Visualize Data Structures and Algorithms with DrawToCode

This is how drawing on other tools looks like:

This is how tool, DrawToCode, looks like:

🌳Don't use pen and paper—use DrawToCode and help save trees!🌳

How to Track Data Structures and Algorithms with DrawToCode

Why Use DrawToCode?

Interactive Whiteboard

Track once and Remember Forever!!!💯

Trusted by Students

Perfect For
|