DSA Topics

A Tree Data Structure can be traversed in following ways:

Depth First Search or DFS

• Inorder Traversal - LDR
• Preorder Traversal - DLR

• Postorder Traversal - LRD
  Level Order Traversal or Breadth First Search or BFS

• Boundary Traversal

• Diagonal Traversal

226. Invert Binary Tree

class Solution 
{
    public TreeNode invertTree(TreeNode root)
    {//we are doing the postorder traversal because we are first knowing about the child and then about the parent //Bottom Up Approach

        if(root == null)//base casewe hit the null node 
            return null;//we just return null saying that no node is there its empty 

        TreeNode left= invertTree(root.left);//Recursing down the left subtree//knowing about the left child //LEFT
        TreeNode right= invertTree(root.right);//Recursing down the right subtree//knowing about the right child //RIGHT

        //ROOT
        //just swapping the pointers, to just alternate the node 
        root.left= right;//root left is pointing to right child
        root.right= left;//root right is pointing to left child

        return root;//returning the root to maintain the backward link//And to tell the parent that I am present
    }
}

Sorting 1

---

## Selection Sort

---

Selection sort is a simple sorting algorithm that works by repeatedly selecting the minimum element from the unsorted part of the array and swapping it with the first unsorted element. The algorithm maintains two subarrays: the sorted part and the unsorted part. As it progresses, the sorted part expands, and the unsorted part shrinks until the entire array is sorted.

Here's a Java implementation of the selection sort algorithm:

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            // Assume the current element is the minimum
            int minIndex = i;

            // Find the index of the minimum element in the unsorted part of the array
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Original Array:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Explanation:

1. The selectionSort method takes an array arr as input and sorts it in ascending order.
2. It iterates through the array, considering each element as the minimum.
3. It then searches for the minimum element in the remaining unsorted part of the array by comparing it with the rest of the elements.
4. Once the minimum element is found, it swaps it with the first unsorted element, expanding the sorted part of the array.
5. The process repeats until the entire array is sorted.

In the example provided, the original array {64, 25, 12, 22, 11} is sorted using selection sort, and the sorted array is {11, 12, 22, 25, 64}.

##Bubble Sort

Bubble sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire list is sorted. The name "bubble sort" comes from the way smaller elements "bubble" to the top of the list as the algorithm progresses.

Here's a Java implementation of the bubble sort algorithm:

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = n-1; i>=0; i--) {
            swapped = false;
            for (int j = 0; j <= i-1; j++) {
                // Compare adjacent elements
                if (arr[j] > arr[j + 1]) {
                    // Swap them if they are in the wrong order
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // If no two elements were swapped in the inner loop, the array is already sorted
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original Array:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

The best time complexity when array is sorted - n
if not sorted - n2

Explanation:

1. The bubbleSort method takes an array arr as input and sorts it in ascending order using the bubble sort algorithm.
2. It uses a boolean variable swapped to keep track of whether any swaps were made during a pass through the array. If no swaps occur during a pass, it means the array is already sorted, and the algorithm can terminate early.
3. The outer loop runs for n-1 passes, where n is the number of elements in the array.
4. The inner loop compares adjacent elements and swaps them if they are in the wrong order.
5. After each pass, the largest element among the unsorted elements "bubbles up" to its correct position at the end of the array.
6. The algorithm repeats this process until the entire array is sorted.

In the example provided, the original array {64, 34, 25, 12, 22, 11, 90} is sorted using bubble sort, and the sorted array is {11, 12, 22, 25, 34, 64, 90}.