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 BFSBoundary 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:
- The
selectionSort
method takes an arrayarr
as input and sorts it in ascending order. - It iterates through the array, considering each element as the minimum.
- It then searches for the minimum element in the remaining unsorted part of the array by comparing it with the rest of the elements.
- Once the minimum element is found, it swaps it with the first unsorted element, expanding the sorted part of the array.
- 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:
- The
bubbleSort
method takes an arrayarr
as input and sorts it in ascending order using the bubble sort algorithm. - 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. - The outer loop runs for
n-1
passes, wheren
is the number of elements in the array. - The inner loop compares adjacent elements and swaps them if they are in the wrong order.
- After each pass, the largest element among the unsorted elements "bubbles up" to its correct position at the end of the array.
- 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}
.