Amol Pawar

Sorting algorithms are fundamental tools in computer science used to organize data efficiently. Sorting algorithms are techniques used to rearrange elements in a list or array in a specific order. The order could be ascending or descending based on certain criteria, such as numerical value or alphabetical order. Sorting algorithms play a crucial role in various applications, including databases, search algorithms, and more.

In Java, sorting algorithms can be implemented using various approaches, each with its unique characteristics and performance implications. In Java, there are various sorting algorithms, each with its advantages and disadvantages. In this guide, we’ll explore some of the most commonly used sorting algorithms, including their implementations, complexities, and use cases.

Sorting algorithms in Java : Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element per iteration and then finding its correct position in the sorted array.

public int[] insertionSort(int[] list) {
   
  int i;   // Counter for outer loop
  int j;   // Counter for inner loop

  int key;    // To hold the key value purpose we use it 

  int temp;   // It will be helpful while swapping values 

  for(i = 1; i < list.length; i++) {
     // Outer for loop starts with 1 and checks till the end value.
     // Here we consider the 0th element is already sorted that's why we start from 1
  
     key = list[i];   // It is our key value which is list[i] for every iteration  
     j = i - 1;         // It will start point of comparison moving downwards till 0 
   
     // We end the while loop when j value reaches 0 or when the key value is no longer smaller than the value
     while(j >= 0 && key < list[j]) {
       // Swap the values using the temp variable and arrange them in increasing order        
       temp = list[j];
       list[j] = list[j + 1];
       list[j + 1] = temp;
       j--;     // Decreasing j by 1 as we move towards the left 
     }

   }
   
  return list;
}

This insertionSort method implements the insertion sort algorithm for sorting an array of integers in increasing order. It iterates through the array, considering each element as a key and inserting it into the correct position in the sorted subarray to its left. The inner loop compares the key with the elements to its left and swaps them if necessary to maintain the sorted order. Finally, it returns the sorted array.

Explanation

Given an array of integers, sort them in increasing order using insertion sort:

Initial array: 5, 8, 1, 3, 9, 6

Definition of sorted: All items to the left are smaller. For example, 5 is already considered sorted as there are no elements to its left.

So, we start our insertion sort process from index 1:

1. Key (k) = 8. Compare k < 5? No. So, 8’s position is correct. Consider 5 and 8 as sorted.
2. Next, at index 2:
   • Key (k) = 1.
   • Compare k < 8? Yes, swap: 5, 1, 8, 3, 9, 6.
   • Compare k < 5? Yes, swap: 1, 5, 8, 3, 9, 6.
   • Element till index 2 is sorted.
3. Start at index 3:
   • Key (k) = 3.
   • Compare k < 8? Yes, swap: 1, 5, 3, 8, 9, 6.
   • Compare k < 5? Yes, swap: 1, 3, 5, 8, 9, 6.
   • Compare k < 1? No, no swap.
   • Elements till index 3 are now sorted.
4. Start at index 4:
   • Key (k) = 9.
   • Compare k < 8? No, no swap. Also, all elements left of 8 are sorted, indicating 9’s position is correct.
   • Elements till index 4 are also sorted.
5. Start at index 5:
   • Key (k) = 6.
   • Compare k < 9? Yes, swap: 1, 3, 5, 8, 6, 9.
   • Compare k < 8? Yes, swap: 1, 3, 5, 6, 8, 9.
   • Compare k < 5? No, no swap. End of loop.

Finally, we obtain the sorted list using insertion sort. Final array: {1, 3, 5, 6, 8, 9}

Note: Insertion Sort is not a fast sorting algorithm as it uses nested loops to shift items into place. It is useful only for small datasets. It runs in O(n^2) time complexity and O(1) space complexity.

Selection Sort

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the array and moves it to the beginning. This process continues until the entire array is sorted.

public int[] selectionSort(int[] list) {
    int i; // Outer loop counter
    int j; // Inner loop counter
    int minValue; // To track minimum value
    int minIndex; // To track the index of the minimum value in the array
    int temp = 0; // For swapping purposes

    // Let's consider this array: 7, 8, 5, 4, 9, 2

    // Outer loop should iterate from 0 to 5 (i.e., 6 iterations)
    // So the outer loop should be: for i = 0 to 5
    for (i = 0; i < list.length; i++) {
        // Initialize minValue and minIndex to the first unsorted item each time through the outer loop
        minValue = list[i];
        minIndex = i;

        // Inner loop starts at the first unsorted item and continues through the last item in the list
        // So the inner loop should be: for j = i to 5
        for (j = i; j < list.length; j++) {
            // Inside the inner loop, if the list item is less than the current minValue,
            // update minValue and store its index in minIndex
            if (list[j] < minValue) {
                minValue = list[j];
                minIndex = j;
            }
        }

        // After that, we check if the minValue is less than the value at the current index of the outer loop
        // If yes, then swap that value with the value at minIndex
        if (minValue < list[i]) {
            temp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = temp;
        }
    }
    return list;
}

This selectionSort method implements the selection sort algorithm for sorting an array of integers in increasing order. It iterates through the array, finding the minimum element in the unsorted part of the array and swapping it with the first unsorted element. This process repeats until the entire array is sorted. Finally, it returns the sorted array.

Explanation

Selection Sort: It finds the smallest item from the unsorted part of the list and moves it to the first element of the list while performing selection sort.

Consider this array: 7, 8, 5, 4, 9, 2 // also imagine indices from 0 to 5.

So initially, our minValue is 7 and minIndex is 0.

• Now, comparison:
  • Is 8 < minValue (7)? No.
  • Is 5 < minValue (7)? Yes, the new minValue is 5 and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4 and minIndex is 3.
  • Is 9 < minValue (4)? No. Is 2 < minValue (4)? Yes, the new minValue is 2 and minIndex is 5.

We found our first smallest element, so we swap that element with the first element ==> 2, 8, 5, 4, 9, 7.

• Our second iteration starts with index 1, so our first element is 8, and minValue is 8, with minIndex as 1. Now, start comparison toward the right side of 8.
  • Is 5 < minValue (8)? Yes, the new minValue is 5, and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4, and minIndex is 3.
  • Is 9 < minValue (4)? No.
  • Is 7 < minValue (4)? No.

We found our smallest element for the second iteration, so we swap it with the first element ==> 2, 4, 5, 8, 9, 7.

• Now, start comparison towards the right side of 5, and we see that 5 is the smallest element among them, so there’s no need to swap.

• Again, we start comparison towards the right side of 8. So, minValue is 8, and minIndex is 3.
  • Is 9 < minValue (8)? No.
  • Is 7 < minValue (8)? Yes, the new minValue is 7, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 9, 8.

• Now, for the next iteration, minValue is 9, and minIndex is 4.
  • Is 8 < minValue (9)? Yes, the new minValue is 8, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 8, 9.

Note: Selection Sort is not a fast sorting algorithm because it uses nested loops to sort. It is useful only for small datasets means suitable for small arrays or when auxiliary memory is limited. It runs in O(n^2) time complexity and O(1) space complexity.

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 pass through the list is repeated until the list is sorted.

public int[] bubbleSort(int[] list) {
    int i; // outer loop counter
    int j; // inner loop counter
    int temp = 0; // for swapping purpose

    for (i = 0; i < list.length - 1; i++) { // outer loop iterate till the end
        for (j = 0; j < list.length - 1 - i; j++) { // inner loop iterate till the end where already sorted element bubbled at the end
            if (list[j] > list[j + 1]) { // if we consider two adjacent values then previous value greater means we need to swap them with next value
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
    return list;
}

This bubbleSort method implements the bubble sort algorithm for sorting an array of integers in increasing order. It iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order. This process repeats until the array is sorted. Finally, it returns the sorted array.

Explanation

Bubble Sort: It is a simple sorting algorithm that repeatedly compares adjacent elements in the list and swaps them if they are in the wrong order. This process continues until the list is sorted.

Unsorted list: 5, 8, 1, 6, 9, 2 // Imagine indices from 0 to 5.

So, what is bubble sort?

In bubble sort, we repeatedly compare adjacent items, for example, 5 and 8, so that with every iteration, larger items “bubble” to the right side.

• First iteration:
  • Is 5 > 8? No.
    • Is 8 > 1? Yes ==> Swap ==> 5, 1, 8, 6, 9, 2
      • Is 8 > 6? Yes ==> Swap ==> 5, 1, 6, 8, 9, 2
        • Is 8 > 9? No.
          • Is 9 > 2? Yes ==> Swap ==> 5, 1, 6, 8, 2, 9

• Second iteration:
  • Is 5 > 1? Yes ==> Swap ==> 1, 5, 6, 8, 2, 9
    • Is 5 > 6? No.
      • Is 6 > 8? No.
        • Is 8 > 2? Yes ==> Swap ==> 1, 5, 6, 2, 8, 9

• Third iteration:
  • Is 1 > 5? No.
    • Is 5 > 6? No.
      • Is 6 > 2? Yes ==> Swap ==> 1, 5, 2, 6, 8, 9
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fourth Iteration:
  • Is 1 > 5? No.
    • Is 5 > 2? Yes ==> Swap ==> 1, 2, 5, 6, 8, 9
      • Is 5 > 6? No.
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fifth Iteration:
  • All elements are in sorted order; no need to do any swapping.

Final sorted list: 1, 2, 5, 6, 8, 9

Note: Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is useful only for small data sets. It runs in O(n^2) and O(1) space complexity.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts each half separately, and then merges the sorted halves.

// passing low and high index to this function
// e.g 38,27,43,3,9,82,10 ==> low -> 0 and high -> 6 (size - 1)th index
private void mergeSort(int low, int high) {
    if (low < high)      // base condition
    {
        int mid = low + (high - low) / 2;    // we need to find mid (it is 3 here)
        // perform recursive division into low to mid and then mid + 1 to high
        mergeSort(low, mid);      // 38,27,43,3  ===for next recursive call ===> 38,27 and 43,3 === next recursive call ==> 38 and 27 | 43 and 3 here as we reached base condition where low and high are equal and return back and execute remaining code
        mergeSort(mid + 1, high);   // we start when the above statement executed completely and reached the base case, so now 9,82,10  === for the next recursive call ===> 9,82 and 10  ==== for the next call ===> 9 and 82 | 10 here also we reached the base condition so go back now
        merge(low, mid, high);    // it will just merge the elements according to the sorting order
    }
}

// we pass low, mid, and high value
private void merge(int low, int mid, int high) {
    // for copying purposes means we copy number values to helper[] from low to till high
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    // we tried to sort the numbers[] element and placed them in exact same order
    while (i <= mid && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
        } else {
            numbers[k] = helper[j];
            j++;
        }
        k++;
    }

    // if still some values remain to be placed in sorted order in numbers[] we will do that here
    while (i <= mid) {
        numbers[k] = helper[i];
        k++;
        i++;
    }
}

These methods implement the merge sort algorithm. mergeSort is a recursive method that divides the array into two halves and recursively calls itself on each half until it reaches the base case where low is no longer less than high. Then, the merge method merges the two sorted halves into a single sorted array.

Explanation

Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, recursively calls itself for the two halves, and then merges the two sorted halves.

For example, with an input array like 38, 27, 43, 3, 9, 82, 10:

First, we call mergeSort(0, 6) as the initial entry point.

In mergeSort:

• We find the mid index (low + (high – low) / 2) to split the array into two halves.
• Then, we recursively call mergeSort for the left half (low to mid) and the right half (mid + 1 to high).
• Finally, we merge the sorted halves using the merge function.

In merge:

• We create a helper array to copy elements from the original array.
• We iterate through the two halves, comparing elements and merging them into the original array in sorted order.
• If any elements remain in the left half after merging, we copy them back to the original array.

Let’s go through the merge sort algorithm step by step:

1. Initial array: {38, 27, 43, 3, 9, 82, 10}
2. Initial call to mergeSort(0, 6):
   • Since low (0) is less than high (6), we proceed.
   • Calculate mid = 0 + (6 – 0) / 2 = 3
3. Recursive call 1: mergeSort(0, 3)
   • Since low (0) is less than high (3), we proceed.
   • Calculate mid = 0 + (3 – 0) / 2 = 1
4. Recursive call 2a: mergeSort(0, 1)
   • Since low (0) is less than high (1), we proceed.
   • Calculate mid = 0 + (1 – 0) / 2 = 0
5. Recursive call 2b: mergeSort(1, 3)
   • Since low (1) is less than high (3), we proceed.
   • Calculate mid = 1 + (3 – 1) / 2 = 2
6. Recursive call 3: mergeSort(1, 2)
   • Since low (1) is less than high (2), we proceed.
   • Calculate mid = 1 + (2 – 1) / 2 = 1
7. Recursive call 4: mergeSort(2, 3)
   • Since low (2) is less than high (3), we proceed.
   • Calculate mid = 2 + (3 – 2) / 2 = 2
8. Back to Recursive call 4: merge(1, 1, 2)
   • Helper array: {27, 43, 43, 3, 9, 82, 10}
   • i = 1, j = 2, k = 1
   • Compare helper[i] (27) with helper[j] (43), place the smaller one (27) in numbers[k] (numbers[1]), increment i and k.
   • numbers: {38, 27, 43, 3, 9, 82, 10}
   • Increment k to 2 and i to 2.
9. Back to Recursive call 3: merge(1, 1, 3)
   • Helper array: {27, 38, 43, 3, 9, 82, 10}
   • i = 1, j = 3, k = 1
   • Compare helper[i] (27) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[1]), increment j and k.
   • numbers: {38, 3, 43, 3, 9, 82, 10}
   • Increment k to 2 and j to 4.
   • Compare helper[i] (27) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[2]), increment j and k.
   • numbers: {38, 3, 9, 3, 9, 82, 10}
   • Increment k to 3 and j to 5.
   • Compare helper[i] (27) with helper[j] (82), place the smaller one (27) in numbers[k] (numbers[3]), increment i and k.
   • numbers: {38, 3, 9, 27, 9, 82, 10}
   • Increment k to 4 and i to 2.
10. Back to Recursive call 2a: merge(0, 0, 1)
    • Helper array: {38, 38, 9, 27, 9, 82, 10}
    • i = 0, j = 1, k = 0
    • Compare helper[i] (38) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[0]), increment j and k.
    • numbers: {3, 3, 9, 27, 9, 82, 10}
    • Increment k to 1 and j to 2.
    • Compare helper[i] (38) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[1]), increment j and k.
    • numbers: {3, 9, 9, 27, 9, 82, 10}
    • Increment k to 2 and j to 3.
    • Compare helper[i] (38) with helper[j] (27), place the smaller one (27) in numbers[k] (numbers[2]), increment i and k.
    • numbers: {3, 9, 27, 27, 9, 82, 10}
    • Increment k to 3 and i to 1.
11. Back to Recursive call 1: merge(0, 1, 3)
    • Helper array: {3, 9, 27, 38, 9, 82, 10}
    • i = 0, j = 2, k = 0
    • Compare helper[i] (3) with helper[j] (9), place the smaller one (3) in numbers[k] (numbers[0]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 1 and i to 1.
    • Compare helper[i] (9) with helper[j] (27), place the smaller one (9) in numbers[k] (numbers[1]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 2 and i to 2.
    • Compare helper[i] (27) with helper[j] (38), place the smaller one (27) in numbers[k] (numbers[2]), increment j and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 3 and j to 3.
12. Final array: {3, 9, 27, 38, 9, 82, 10}

This process continues until the entire array is sorted. The merge sort algorithm effectively divides the array into smaller segments, sorts them individually, and then merges them back together in sorted order.

Note: Merge Sort has a time complexity of O(n log n) in the average and worst cases, and O(n) in the best case, making it efficient for large datasets and O(n) space complexity.

Quick Sort

Quick Sort is another divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It then recursively sorts the subarrays.

private void quickSort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];  // Choosing the pivot element

    // Partitioning the array
    while (i <= j) {
        // Finding element on the left side that should be on the right
        while (numbers[i] < pivot) {
            i++;
        }
        // Finding element on the right side that should be on the left
        while (numbers[j] > pivot) {
            j--;
        }

        // If we found a value on the left that should be on the right and vice versa, swap them
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    // Recursively sort the left and right partitions
    if (low < j) {
        quickSort(low, j);
    }
    if (i < high) {
        quickSort(i, high);
    }
}

This quickSort method implements the Quick Sort algorithm. It chooses a pivot element (here, the middle element) and partitions the array into two sub-arrays such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the sub-arrays until the entire array is sorted. The exchange method is assumed to swap the values at two indices in the array.

Explanation

Quick Sort is a divide and conquer algorithm. In this algorithm, the original data is divided into two parts, sorted individually, and then combined.

suppose

{6,4,2,1,5,3} is an array where low is pointing to 0th index and high is pointing to last index.

means,

• Set low to 0 and high to array.length - 1, then pass these values to quickSort(low, high).
• Assign low to i, which is the left side counter of the pivot, and assign high to j, which is the right side counter of the pivot.
• Find the pivot. What is a pivot? A pivot is a point we consider while sorting. We arrange smaller values than the pivot to its left side and greater values to its right side. We can take any value as the pivot, but it’s best to take it randomly. Here, we use the middle element as the pivot.
• We will check i <= j. If low becomes greater than high, we stop our following checks: i) First, we check the left side of the pivot to find any greater value than the pivot. If we find such a value, we terminate the while loop. Otherwise, we iterate until we reach the pivot. Since we don’t have any problem with values smaller than the pivot (as those should be on the left side), we increment i and move towards the pivot to check the next value. ii) After completing the left side (either by complete check or finding a greater value, terminating the while loop), we look at the right side of the pivot. We apply the same logic: while(any value > pivot). If true, we decrement j. If we find any smaller value than the pivot, the while loop terminates. iii) So, in the above two cases, we find whether the left side of the pivot will contain any greater value than the pivot or whether the right side of the pivot will contain any smaller value than the pivot. Because we sort the values according to the pivot, if we find a smaller value to the right and a larger value to the left, we need to place them on their respective sides. For this purpose, we use another if() condition: if i is not greater than j, then only do we exchange the values. Finally, we increment i and decrement j.
• As we perform sorting according to the pivot, only small values are placed on the left side of the pivot and large values are placed on the right side. However, we notice that neither the left side nor the right side is sorted.

For example, with an array like 6, 4, 2, 1, 5, 3:

• We call quickSort(0, 5) initially, where low = 0 and high = 5.
• We select a pivot element, here we choose the middle element, which is 2.
• We partition the array around the pivot, ensuring that elements less than the pivot are on the left and elements greater than the pivot are on the right.
• We recursively call quickSort for the left and right partitions, ensuring that all elements are sorted individually.
• We repeat this process until the entire array is sorted.

Let’s go through the Quick Sort algorithm step by step:

1. Initial array: {6, 4, 2, 1, 5, 3}
2. Initial call to quickSort(0, 5):
   • i = 0, j = 5
   • Pivot = numbers[0 + (5 – 0) / 2] = numbers[2] = 2
3. While loop (i=0, j=5):
   • i moves from left to right until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves from right to left until it finds a value less than or equal to the pivot. (j stops at 3)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 4, 2, 1, 5, 6}
   • Increment i and decrement j (i = 1, j = 4)
4. While loop (i=1, j=4):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 1)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 2, j = 3)
5. While loop (i=2, j=3):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 2)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 2)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array remains {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 3, j = 1)
6. While loop termination (i=3, j=1):
   • i > j, so the while loop terminates.
7. Recursive call 1: quickSort(0, 1)
   • This is the left side partition.
   • i = 0, j = 1
   • Subarray: {3, 1}
   • Pivot = numbers[0] = 3
   • While loop terminates immediately as i > j.
8. Recursive call 2: quickSort(3, 5)
   • This is the right side partition.
   • i = 3, j = 5
   • Subarray: {4, 5, 6}
   • Pivot = numbers[3] = 4
   • While loop terminates immediately as i > j.
9. Final sorted array: {1, 2, 3, 4, 5, 6}

This process continues recursively until all partitions have size 1 or less, meaning the array is sorted. The Quick Sort algorithm effectively divides the array into smaller partitions, sorts them individually, and then combines them to get the sorted array.

Note: Quick Sort has a time complexity of O(n log n) in the average and best cases, and O(n^2) in the worst case. However, its average case performance is typically much better than other O(n^2) algorithms like Bubble Sort and Selection Sort. It has space complexity O(log n) to O(n). Also, Quick Sort is efficient and widely used, but it has a higher worst-case time complexity compared to Merge Sort.

Conclusion

In this guide, we’ve covered several sorting algorithms in Java, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort. Each algorithm has its advantages and disadvantages, and the choice of algorithm depends on factors such as the size of the dataset, memory constraints, and desired performance characteristics. By understanding these sorting algorithms, you can choose the most appropriate one for your specific use case and optimize the efficiency of your Java applications.

Graphs are fundamental data structures in computer science and are widely used to model complex relationships between entities. They are versatile and can represent a variety of real-world scenarios such as social networks, transportation networks, and computer networks. In this blog post, we’ll delve into some essential graph algorithms implemented in Java, covering Depth-First Search (DFS), Breadth-First Search (BFS), Dijkstra’s Shortest Path Algorithm, detecting cycles in a directed graph, and performing a topological sort.

Understanding Graphs

Before diving into the algorithms, let’s briefly review what graphs are. We know that data arranged in a linear manner is called linear data structures, such as Arrays, LinkedLists, Stacks, and Queues. Whereas, when data is stored non-linearly, it is referred to as non-linear data structures, such as Trees and Graphs. A graph consists of a set of vertices (nodes) and a set of edges (connections) that establish relationships between these vertices. Edges can be directed or undirected, depending on whether they have a specific direction or not. Graphs can also be weighted, where each edge has an associated weight or cost.

A graph is a powerful non-linear data structure consisting of two components:

• Vertices (nodes): Represent individual entities or data points. Think of them as points on a map.
• Edges: Represent connections between vertices, indicating relationships or interactions. Edges can be bidirectional (undirected) or unidirectional (directed), like arrows showing one-way relationships.

A graph G is an ordered pair consisting of a set V of vertices and a set E of edges.

G = (V,E)

In an ordered pair, (a,b) is not equivalent to (b,a) if a ≠ b.

In an unordered pair, {a,b} equals {b,a}.

Edges:

• Directed: (u,v) i.e., u → v
• Undirected: {u,v} i.e., u — v

Example:

V = {v1, v2, v3, v4, v5, v6, v7, v8} // Set of vertices

E = { {v1, v2}, {v1, v3}, {v2, v4}, {v3, v5}, {v4, v6}, {v5, v7}, {v6, v8}, {v7, v8}, {v2, v5}, {v3, v6} }

Graph Examples

Consider a social network like Facebook. Users are represented as vertices, and friendships are represented as edges. If A and B are friends, we can have either a directed edge A -> B (meaning A follows B) or an undirected edge {A, B} (meaning they follow each other).

Common Graphs Examples

• Maps: Represent cities as vertices and roads as edges (weighted to denote distance).
• World Wide Web: Represent web pages as vertices and hyperlinks as directed edges pointing from source pages to destination pages.
• File systems: Represent directories as vertices and subdirectory/file connections as edges.

Graph Representations:

• Adjacency Matrix: Square matrix, where (i,j) reflects the edge weight between vertices i and j. Suitable for dense graphs with many edges.
• Adjacency List: Array or list of lists, where each index stores connections for a specific vertex. More efficient for sparse graphs with fewer edges.

Implementing Graphs in Java

To start, we’ll implement a simple graph representation in Java. We’ll use an adjacency list to store the graph, which is a list of lists where each list represents the neighbors of a particular vertex.

import java.util.*;

class Graph {
    private int V; // Number of vertices
    private LinkedList<Integer> adjList[]; // Adjacency list representation

    // Constructor
    Graph(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList<>();
    }

    // Function to add an edge to the graph
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // Getter for the adjacency list of a vertex
    LinkedList<Integer> getAdjList(int v) {
        return adjList[v];
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        for (int i = 0; i < graph.V; i++) {
            LinkedList<Integer> list = graph.getAdjList(i);
            System.out.print("Adjacency list of vertex " + i + ": ");
            for (Integer node : list) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }
}

This Graph class represents an undirected graph using an adjacency list representation. It has a constructor to initialize the graph with a given number of vertices. The addEdge method adds an edge between two vertices. The getAdjList method returns the adjacency list of a specified vertex.

The main method demonstrates how to use the Graph class by creating a graph with 4 vertices and adding some edges. Then, it prints the adjacency list of each vertex.

Common Types of Graphs

Here are some common types of graphs and their java implementations:

Directed Graphs (Digraphs)

Directed graphs, also known as digraphs, are graphs in which edges have a direction associated with them. This means that the relationship between nodes is one-way. They are used to model relationships like dependencies, flows, or hierarchical structures.

   A
  ↗ ↘
 B   C
  ↘ ↗
   D

• Vertices are represented by letters: A, B, C, D.
• Arrows indicate the direction of the edges.
• Arrows point from the source vertex to the destination vertex, representing a directed edge from the source to the destination.

Implementation: In Java, you can implement a directed graph using adjacency lists or adjacency matrices. Here’s a basic example of implementing a directed graph using adjacency lists:

import java.util.*;

class Digraph {
    private int V;
    private List<Integer>[] adj;

    public Digraph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

Undirected Graphs

Undirected graphs are graphs in which edges do not have any direction associated with them. The relationship between nodes is bidirectional. They are used to model symmetric relationships, such as friendships in social networks or connections in a network.

   A
  / \
 /   \
B --- C
 \   /
  \ /
   D

• Vertices are represented by letters: A, B, C, D.
• Edges are represented by lines connecting the vertices.
• Each line connects two vertices, representing an undirected edge between them.

Implementation: Similar to directed graphs, undirected graphs can be implemented using adjacency lists or adjacency matrices. Here’s a basic example of implementing an undirected graph using adjacency lists:

import java.util.*;

class Graph {
    private int V;
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

Weighted Graphs

Weighted graphs are graphs in which each edge has an associated weight or cost. They are used to model scenarios where the relationship between nodes has a numerical value associated with it, such as distances between cities or costs of transportation.

   
   A
2/   \4
/     \
B--5-- C
\1   3/
 \   /
   D

• Vertices are represented by letters: A, B, C, D.
• Edges are represented by lines connecting the vertices.
• Each line connecting two vertices represents an edge.
• Beside each edge, there is a number indicating the weight of that edge.
• For example, the edge between vertices A and B has a weight of 2, the edge between vertices B and D has a weight of 1, etc.

Implementation: Weighted graphs can be implemented similarly to undirected or directed graphs, with the addition of storing weights along with edges. Here’s an example of implementing a weighted graph using adjacency lists:

import java.util.*;

class WeightedGraph {
    private int V;
    private List<Edge>[] adj;

    class Edge {
        int v, w;

        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public WeightedGraph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w, int weight) {
        adj[v].add(new Edge(w, weight));
        adj[w].add(new Edge(v, weight)); // For undirected graphs
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }
}

Graph Algorithms

Now that we have our graph implementation ready, let’s explore some fundamental graph algorithms.

Depth-First Search (DFS) Traversal Algorithm

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of vertices to visit next.

class DFS {
    // Depth-First Search traversal
    void dfsUtil(int v, boolean visited[], Graph graph) {
        visited[v] = true;
        System.out.print(v + " ");

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor])
                dfsUtil(neighbor, visited, graph);
        }
    }

    void dfs(int v, Graph graph) {
        boolean visited[] = new boolean[graph.V];
        dfsUtil(v, visited, graph);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        DFS dfs = new DFS();
        System.out.print("Depth-First Search traversal starting from vertex 2: ");
        dfs.dfs(2, graph);
    }
}

This DFS class contains methods for performing a Depth-First Search (DFS) traversal on a graph. The dfsUtil method is a recursive utility function that performs DFS traversal starting from a specified vertex (v). It marks the vertex as visited, prints its value, and then recursively visits its unvisited neighbors. The dfs method initializes an array to track visited vertices and calls dfsUtil to start the DFS traversal from a specified vertex.

The main method demonstrates how to use the DFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a DFS traversal starting from vertex 2 and prints the traversal result.

Breadth-First Search (BFS) Traversal Algorithm

BFS is another traversal algorithm that explores all the neighboring nodes at the present depth prior to moving on to the nodes at the next depth level.

import java.util.LinkedList;

class BFS {
    // Breadth-First Search traversal
    void bfs(int v, Graph graph) {
        boolean visited[] = new boolean[graph.V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[v] = true;
        queue.add(v);

        while (!queue.isEmpty()) {
            v = queue.poll();
            System.out.print(v + " ");

            LinkedList<Integer> neighbors = graph.getAdjList(v);
            for (Integer neighbor : neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        BFS bfs = new BFS();
        System.out.print("Breadth-First Search traversal starting from vertex 2: ");
        bfs.bfs(2, graph);
    }
}

This BFS class contains a method for performing a Breadth-First Search (BFS) traversal on a graph. The bfs method initializes a boolean array to track visited vertices and a queue to store vertices for traversal. It starts the traversal from a specified vertex (v), marks it as visited, and adds it to the queue. Then, it repeatedly dequeues vertices from the queue, prints them, and adds their unvisited neighbors to the queue.

The main method demonstrates how to use the BFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a BFS traversal starting from vertex 2 and prints the traversal result.

Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph. It maintains a priority queue to continuously select the vertex with the smallest distance from the source.

import java.util.*;

class Dijkstra {
    // Dijkstra's Shortest Path Algorithm
    void dijkstra(int src, Graph graph) {
        int V = graph.V;
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
        pq.add(src);

        while (!pq.isEmpty()) {
            int u = pq.poll();
            LinkedList<Integer> neighbors = graph.getAdjList(u);
            for (Integer v : neighbors) {
                int weight = 1; // Assuming unweighted graph, modify for weighted graph
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(v);
                }
            }
        }

        // Print shortest distances
        System.out.println("Shortest distances from source vertex " + src + ":");
        for (int i = 0; i < V; i++) {
            System.out.println("Vertex " + i + ": " + dist[i]);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        Dijkstra dijkstra = new Dijkstra();
        int sourceVertex = 0;
        dijkstra.dijkstra(sourceVertex, graph);
    }
}

This Dijkstra class contains a method for finding the shortest path distances from a source vertex to all other vertices in a graph using Dijkstra’s algorithm. The dijkstra method initializes an array to store shortest distances (dist), initializes all distances to infinity except for the source vertex distance which is set to 0. It then uses a priority queue (pq) to greedily select the vertex with the shortest distance and updates the distances to its neighbors if a shorter path is found. Finally, it prints the shortest distances from the source vertex to all other vertices.

The main method demonstrates how to use the Dijkstra class by creating a graph with 6 vertices and adding some edges. Then, it performs Dijkstra’s algorithm starting from a specified source vertex and prints the shortest distances to all other vertices.

Detecting Cycles in a Directed Graph

Detecting cycles in a directed graph is crucial in various applications such as deadlock detection and task scheduling. We’ll use a modified DFS approach to detect cycles.

class CycleDetection {
    boolean isCyclicUtil(int v, boolean visited[], boolean recStack[], Graph graph) {
        if (recStack[v])
            return true;

        if (visited[v])
            return false;

        visited[v] = true;
        recStack[v] = true;

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (isCyclicUtil(neighbor, visited, recStack, graph))
                return true;
        }

        recStack[v] = false;
        return false;
    }

    boolean isCyclic(Graph graph) {
        boolean visited[] = new boolean[graph.V];
        boolean recStack[] = new boolean[graph.V];

        for (int i = 0; i < graph.V; i++) {
            if (isCyclicUtil(i, visited, recStack, graph))
                return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        CycleDetection cycleDetection = new CycleDetection();
        if (cycleDetection.isCyclic(graph))
            System.out.println("The graph contains a cycle");
        else
            System.out.println("The graph doesn't contain a cycle");
    }
}

This CycleDetection class contains methods to detect cycles in a graph using depth-first search (DFS). The isCyclicUtil method recursively checks if there is a cycle starting from a given vertex (v) by maintaining a boolean array (recStack) to keep track of the vertices in the current recursion stack. If a vertex is visited and also present in the recursion stack, it indicates the presence of a cycle. The isCyclic method iterates through all vertices in the graph and calls isCyclicUtil for each vertex to check for cycles.

The main method demonstrates how to use the CycleDetection class by creating a graph with 4 vertices and adding some edges. Then, it checks if the graph contains a cycle and prints the result.

Topological Sorting of a Graph

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

import java.util.*;

class TopologicalSort {
    Stack<Integer> stack = new Stack<>();

    void topologicalSortUtil(int v, boolean visited[], Graph graph) {
        visited[v] = true;

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor])
                topologicalSortUtil(neighbor, visited, graph);
        }

        stack.push(v);
    }

    void topologicalSort(Graph graph) {
        int V = graph.V;
        boolean visited[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i])
                topologicalSortUtil(i, visited, graph);
        }

        // Print topological order
        System.out.println("Topological order:");
        while (!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topologicalSort(graph);
    }
}

This TopologicalSort class contains methods to perform topological sorting on a directed acyclic graph (DAG) using depth-first search (DFS). The topologicalSortUtil method recursively traverses the graph, marking visited vertices and pushing them onto a stack after visiting all of their neighbors. The topologicalSort method initiates DFS traversal for each vertex and then prints the topological order by popping vertices from the stack.

The main method demonstrates how to use the TopologicalSort class by creating a graph with 6 vertices and adding directed edges between them. Then, it performs topological sorting and prints the topological order.

Conclusion

In this blog post, we explored several essential graph algorithms implemented in Java, including DFS, BFS, Dijkstra’s Shortest Path Algorithm, cycle detection in directed graphs, and topological sorting. Understanding these algorithms is crucial for tackling a wide range of graph-related problems efficiently. Feel free to experiment with these implementations and explore further applications in your projects. Happy coding!

Binary trees are a fundamental data structure in computer science, widely used for representing hierarchical data. In this blog post, we will delve into the concept of binary trees, their implementation in Java, traversal algorithms, and some common operations associated with them.

Understanding Binary Trees

What is a Tree?

A tree is a non-linear data structure used for storing data. It is comprised of nodes and edges without any cycles. Each node in a tree can point to n number of other nodes within the tree. It serves as a way to represent hierarchical structures, with a parent node called the root and multiple levels of additional nodes.

• It’s a non-linear data structure used for storing data
• It is made up of nodes and edges without having any cycle. // its so important
• Each node in a tree can point to n number of nodes in a tree
• It is a way of representing a hierarchical structure with a parent node called a root and many levels of additional nodes

What is a Binary Tree?

A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node of the tree is called the root node. Each node contains a data element and references to its left and right children (or null if the child does not exist).

In simple words, A tree is called a binary tree if each node has zero, one, or two children.

       1
      / \
     2   3
    / \
   4   5

Binary trees are commonly used in various applications such as expression trees, binary search trees, and more.

How to represent a Binary Tree in java?

TreeNode Representation:

null<-----|left|data|right|------>null

Structure of TreeNode in a Binary Tree:

To represent a binary tree in Java, we can create a TreeNode class to define the structure of each node in the tree. Here’s how we can do it:

public class TreeNode {
    private int data;      // Data of the node
    private TreeNode left; // Pointer to the left child node
    private TreeNode right; // Pointer to the right child node
    
    // Constructor to initialize the node with data
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
    
    // Getters and setters for the data, left, and right pointers
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

In this TreeNode class:

• Each node has a data field to store the value of the node.
• Each node has a left field to store a reference to its left child node.
• Each node has a right field to store a reference to its right child node.
• The constructor initializes the node with the given data and sets both left and right pointers to null initially.

With this TreeNode class, you can create instances of the TreeNode class to represent each node in the binary tree. You can then use these instances to build the binary tree by setting the left and right pointers of each node accordingly. The root of the binary tree is typically represented by a reference to the topmost node in the tree. Initially, if the tree is empty, the root reference is set to null. As you add nodes to the tree, you update the root reference accordingly.

In simple words, Initially, the root node points to null. When we create any temporary node to insert into the tree, such as a temporary node with 15 as its data and left and right node pointers pointing to null, we can then add more nodes to the left or right.

How to implement a binary tree in java?

Let’s start by implementing a basic binary tree structure in Java:

public class BinaryTree {

  private TreeNode root;      // Created one root node of TreeNode type
 
  private class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int data;

    public TreeNode(int data) {
       this.data = data;
    }
  }

  public void createBinaryTree() {
     TreeNode first = new TreeNode(1);
     TreeNode second = new TreeNode(2);
     TreeNode third = new TreeNode(3);
     TreeNode fourth = new TreeNode(4);
     TreeNode fifth = new TreeNode(5);

     root = first;     // root ---> first
     first.left = second;
     first.right = third;  // second <--- first ---> third

     second.left = fourth;
     second.right = fifth;
  }

  public static void main(String[] args) {
     BinaryTree bt = new BinaryTree();
     bt.createBinaryTree();
  }
}

This BinaryTree class represents a simple binary tree. It has a nested class TreeNode which represents each node in the binary tree. The createBinaryTree method initializes the tree structure by creating nodes and linking them appropriately. Finally, the main method demonstrates creating an instance of BinaryTree and initializing it.

Traversal Algorithms

Traversal is the process of visiting all the nodes in a tree in a specific order. There are three common methods for traversing binary trees:

1. In-order traversal: Visit the left subtree, then the root, and finally the right subtree.
2. Pre-order traversal: Visit the root, then the left subtree, and finally the right subtree.
3. Post-order traversal: Visit the left subtree, then the right subtree, and finally the root.

Let’s implement these traversal algorithms in Java.

Pre-Order Traversal Of Binary Tree in Java

1. Visit the root node.
2. Traverse the left subtree in pre-order fashion.
3. Traverse the right subtree in pre-order fashion.

Recursive Pre-Order Traversal

It recursively traverses the tree in the following order: root, left subtree, right subtree.

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

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it prints the data of the current node, traverses the left subtree recursively, and then traverses the right subtree recursively.

Consider the following binary tree:

     1
    / \
   2   3
  / \
 4   5

In pre-order traversal, the order of node visits would be: 1, 2, 4, 5, 3.

Here’s how the execution progresses:

1. pre_order_traversal(1) – Visit root node 1.
2. pre_order_traversal(2) – Visit root node 2.
3. pre_order_traversal(4) – Visit root node 4.
4. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(4)), finish left subtree traversal.
5. pre_order_traversal(5) – Visit root node 5.
6. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(5)), finish left subtree traversal.
7. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(2)), finish left subtree traversal.
8. pre_order_traversal(3) – Visit root node 3.
9. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(3)), finish right subtree traversal.
10. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

Pre-order traversal: 1 2 4 5 3

In this execution, we maintain a call stack. For each method call, we track the line number and the root node being passed to that method. When we reach the base condition, we backtrack to the previous calls and execute the next steps.

Iterative Pre-Order Traversal Of Binary Tree

Iterative pre-order traversal is a way to traverse a binary tree iteratively, without using recursion. we utilize the stack data structure. Initially, we push the root node onto the stack. While the stack is not empty, we iterate using a while loop and perform pre-order traversal operations. As long as the stack is not empty, we pop the top node from the stack and assign it to the temp node. We then print its data. Since in pre-order traversal, we first visit the left node and then the right node, while pushing nodes into the stack, we need to push the right node first and then the left node so that we process the left node first (due to LIFO).

public void IterativePreOrder() {
    if(root == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode temp = stack.pop();
        System.out.println(temp.data);
        if(temp.right != null) {
            stack.push(temp.right);
        }
        if(temp.left != null) {
            stack.push(temp.left);
        }
    }
}

This method iterativePreOrder performs an iterative pre-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It prints the data of each node as it visits them. If a node has a right child, it is pushed onto the stack first so that it is visited after the left child (since pre-order traversal visits the left subtree before the right subtree). Finally, the method returns once all nodes have been visited.

Consider the following binary tree:

       1
      / \
     2   3
    / \
   4   5

The iterative pre-order traversal will visit the nodes in the order: 1, 2, 4, 5, 3.

Here’s how the execution goes step by step:

1. Start with an empty stack and initialize the current node as the root.
2. Push the root node onto the stack.
3. While the stack is not empty, do the following:
   • a. Pop the top node from the stack and process it (print its value or perform any other desired operation).
   • b. Push the right child onto the stack if it exists.
   • c. Push the left child onto the stack if it exists.

Let’s execute the algorithm step by step:

1. Start with an empty stack: Stack = []
2. Push the root node (1) onto the stack: Stack = [1]
3. Pop the top node from the stack (1), process it: Output = [1], Stack = []
4. Push the right child (3) onto the stack: Stack = [3]
5. Push the left child (2) onto the stack: Stack = [3, 2]
6. Pop the top node from the stack (2), process it: Output = [1, 2], Stack = [3]
7. Push the right child (5) onto the stack: Stack = [3, 5]
8. Push the left child (4) onto the stack: Stack = [3, 5, 4]
9. Pop the top node from the stack (4), process it: Output = [1, 2, 4], Stack = [3, 5]
10. There’s no left or right child for node 4, so proceed.
11. Pop the top node from the stack (5), process it: Output = [1, 2, 4, 5], Stack = [3]
12. There’s no left or right child for node 5, so proceed.
13. Pop the top node from the stack (3), process it: Output = [1, 2, 4, 5, 3], Stack = []
14. The stack is empty, so the traversal is complete.

The output of the iterative traversal is: [1, 2, 4, 5, 3], which is the pre-order traversal of the given binary tree.

During the execution of iterative pre-order traversal, we follow the described algorithm. We push the root node onto the stack initially. Then, as long as the stack is not empty, we pop nodes from the stack, print their data, and push their right and left children onto the stack accordingly.

In Order Binary Tree traversal

1. Traverse the left subtree in In-order fashion.
2. Visit the root node.
3. Traverse the right subtree in In-order fashion.

In-order traversal of a binary tree involves visiting the left subtree in in-order fashion, then visiting the root node, and finally traversing the right subtree in in-order fashion.

Recursive In-Order Binary Tree Traversal

In Recursive In-order traversal, we visit each node in the tree in the following order:

1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.

public void RecursiveInOrder(TreeNode root) {
    if(root == null) { // base case
        return;
    }
    
    RecursiveInOrder(root.left);
    System.out.print(root.data + " ");
    RecursiveInOrder(root.right);
}

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it recursively traverses the left subtree, then prints the data of the current node, and finally recursively traverses the right subtree.
• This process effectively traverses the tree in an in-order sequence.

Consider the same binary tree:

     1
    / \
   2   3
  / \
 4   5

In in-order traversal, the order of node visits would be: 4, 2, 5, 1, 3.

Here’s how the execution progresses:

1. in_order_traversal(1) – Traverse left subtree.
2. in_order_traversal(2) – Traverse left subtree.
3. in_order_traversal(4) – Visit root node 4.
4. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(4)), finish left subtree traversal.
5. Print root node 2.
6. in_order_traversal(5) – Visit root node 5.
7. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(5)), finish left subtree traversal.
8. Print root node 1.
9. in_order_traversal(3) – Traverse right subtree.
10. Print root node 3.
11. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

In-order traversal:4 2 5 1 3

During the execution of recursive in-order traversal, we maintain a method call stack. For each method call, we keep track of the line number and the root node being passed to that method. Initially, we pass the root node to this method. Then, we visit the left subtree of the root node, print the root node’s data, and finally visit the right subtree of the root node. This tracking of each recursive method call, line number, and root node helps during backtracking.

Iterative In Order Traversal of binary tree in java

In iterative in-order traversal, we visit the left node first, then perform in-order traversal for that node, come back to print the root node’s data, and finally visit the right node to perform its in-order traversal.

To achieve this, we create a stack of TreeNodes and initialize a temp node with the root node. We traverse the tree until the stack is not empty or temp is not null (indicating there are nodes to traverse or backtrack).

If temp is not null, we push it onto the stack and move to its left child. If temp is null, indicating we have reached a leaf node, we pop the top node from the stack, print its data, and move to its right child. This process continues until all nodes are traversed.

public void iterativeInOrderTraversal(TreeNode root) {
   if (root == null) {
     return;
   }

  Stack<TreeNode> stack = new Stack<>();
  TreeNode temp = root;
  while (!stack.isEmpty() || temp != null) {
    if (temp != null) {
      stack.push(temp);
      temp = temp.left;
    } else {
      temp = stack.pop();
      System.out.print(temp.data + " ");
      temp = temp.right;
    }    
  }
}

This method iterativeInOrderTraversal performs an iterative in-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It traverses the left subtree first, then visits the current node, and finally traverses the right subtree. If a node has a left child, it is pushed onto the stack and the left child becomes the current node. If a node does not have a left child or has already been visited, it is popped from the stack, its data is printed, and its right child becomes the current node. The traversal continues until all nodes have been visited and the stack is empty.

Consider the same binary tree:

       1
      / \
     2   3
    / \
   4   5

The iterative in-order traversal will visit the nodes in the order: 4, 2, 5, 1, 3.

Here’s how the execution goes step by step:

1. Start with an empty stack and initialize the current node as the root.
2. Push the root node onto the stack and move to the left child until reaching a null node.
3. When a null node is reached, pop the top node from the stack, process it (print its value or perform any other desired operation), and move to its right child.

Let’s execute the algorithm step by step:

1. Start with an empty stack: Stack = []
2. Push the root node (1) onto the stack and move to the left child: Stack = [1], Current Node = 1
3. Move to the left child of 1 (2) and push it onto the stack: Stack = [1, 2], Current Node = 2
4. Move to the left child of 2 (4) and push it onto the stack: Stack = [1, 2, 4], Current Node = 4
5. The left child of 4 is null, so pop 4 from the stack, process it: Output = [4], Stack = [1, 2], Current Node = 2
6. Move to the right child of 4 (null), so no action needed: Output = [4], Stack = [1, 2], Current Node = 2
7. Process node 2: Output = [4, 2], Stack = [1], Current Node = 2
8. Move to the right child of 2 (5) and push it onto the stack: Stack = [1, 5], Current Node = 5
9. The left child of 5 is null, so process node 5: Output = [4, 2, 5], Stack = [1], Current Node = 5
10. Move to the right child of 5 (null), so no action needed: Output = [4, 2, 5], Stack = [1], Current Node = 5
11. Process node 1: Output = [4, 2, 5, 1], Stack = [], Current Node = 1
12. Move to the right child of 1 (3) and push it onto the stack: Stack = [3], Current Node = 3
13. The left child of 3 is null, so process node 3: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
14. Move to the right child of 3 (null), so no action needed: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
15. The stack is empty, so the traversal is complete.

The output of the traversal is: [4, 2, 5, 1, 3], which is the in-order traversal of the given binary tree.

Post Order traversal of Binary Tree

1. Traverse the left subtree in Post-order fashion.
2. Traverse the right subtree in Post-order fashion.
3. Visit the root node.

Recursive Post-Order Traversal of Binary Tree

In recursive post-order traversal, we visit each node in the tree in the following order:

1. Recursively traverse the left subtree.
2. Recursively traverse the right subtree.
3. Visit the root node.

       1
      / \
     2   3
    / \
   4   5

In post-order traversal, the order of node visits would be: 4, 5, 2, 3, 1.

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

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it recursively traverses the left subtree, then recursively traverses the right subtree, and finally prints the data of the current node.
• This process effectively traverses the tree in a post-order sequence.

Here’s how the execution progresses:

1. post_order_traversal(1) – Traverse left subtree.
2. post_order_traversal(2) – Traverse left subtree.
3. post_order_traversal(4) – Visit root node 4.
4. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(4)), finish left subtree traversal.
5. post_order_traversal(5) – Visit root node 5.
6. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(5)), finish left subtree traversal.
7. Print root node 2.
8. post_order_traversal(3) – Traverse right subtree.
9. Print root node 3.
10. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(3)), finish right subtree traversal.
11. Print root node 1.
12. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

Post-order traversal: 4 5 2 3 1

In recursive post-order traversal, we utilize a method call stack. For each recursive call, we visit the left and right nodes respectively, and then print the data of the root node.

To illustrate this, we maintain a method call stack where we track the line number and the root node being passed to that method. This approach ensures that we visit the left and right subtrees first before printing the data of the root node.

Iterative post-order traversal of a binary tree

Iterative post-order traversal is a bit more complex compared to pre-order and in-order traversals because you need to ensure that you visit the left and right subtrees before processing the root node. One common approach to achieve this iteratively is to use two stacks.

public void iterativePostOrderTraversal(TreeNode root) {
   if (root == null) {
     return;
   }

   Stack<TreeNode> stack1 = new Stack<>();
   Stack<TreeNode> stack2 = new Stack<>();
   stack1.push(root);

   while (!stack1.isEmpty()) {
       TreeNode temp = stack1.pop();
       stack2.push(temp);
       if (temp.left != null) {
           stack1.push(temp.left);
       }
       if (temp.right != null) {
           stack1.push(temp.right);
       }
   }

   while (!stack2.isEmpty()) {
       System.out.print(stack2.pop().data + " ");
   }
}

This method iterativePostOrderTraversal performs an iterative post-order traversal of the binary tree. It starts from the root node and uses two stacks to keep track of nodes to be visited. It pushes nodes onto stack2 in a pre-order traversal (root, right, left) using stack1. After traversing all nodes, it pops nodes from stack2 to print their data, resulting in a post-order traversal (left, right, root). The traversal continues until all nodes have been visited and both stacks are empty.

Here’s how the execution goes step by step:

1. Start with two empty stacks: Stack1 and Stack2. Initialize the current node as the root.
2. Push the root node onto Stack1.
3. While Stack1 is not empty, do the following: a. Pop the top node from Stack1 and push it onto Stack2. b. Push the left child onto Stack1 if it exists. c. Push the right child onto Stack1 if it exists.
4. Once Stack1 is empty, all nodes have been pushed onto Stack2. Pop nodes from Stack2 to get the post-order traversal.

Let’s execute the algorithm step by step:

1. Start with two empty stacks: Stack1 = [], Stack2 = [].
2. Push the root node (1) onto Stack1: Stack1 = [1].
3. Pop the top node from Stack1 (1) and push it onto Stack2: Stack2 = [1].
4. Push the right child (3) onto Stack1: Stack1 = [3].
5. Push the left child (2) onto Stack1: Stack1 = [3, 2].
6. Pop the top node from Stack1 (2) and push it onto Stack2: Stack2 = [1, 2].
7. Push the right child (5) onto Stack1: Stack1 = [3, 5].
8. Push the left child (4) onto Stack1: Stack1 = [3, 5, 4].
9. Pop the top node from Stack1 (4) and push it onto Stack2: Stack2 = [1, 2, 4].
10. Pop the top node from Stack1 (5) and push it onto Stack2: Stack2 = [1, 2, 4, 5].
11. Pop the top node from Stack1 (3) and push it onto Stack2: Stack2 = [1, 2, 4, 5, 3].
12. All nodes have been processed and pushed onto Stack2.
13. Pop nodes from Stack2 to get the post-order traversal: Output = [4, 5, 2, 3, 1].

The output of the traversal is: [4, 5, 2, 3, 1], which is the post-order traversal of the given binary tree.

Level order traversal of a Binary Tree in Java

In level order traversal, also known as breadth-first traversal, we visit each node level by level. To achieve this, we use a queue data structure. Initially, we add the root node to the queue. Then, we iterate while the queue is not empty.

During each iteration, we dequeue a node from the queue and assign it to the temp node. We print the data of this node. If the temp node has left and/or right children, we enqueue them into the queue. This ensures that we traverse the tree level by level, visiting each node before moving on to its children.

This approach is useful for applications like level-wise printing of a binary tree or finding the shortest path in a graph represented as a tree.

if (root == null) {
   return;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
  TreeNode temp = queue.poll();
  System.out.print(temp.data + " ");
  if (temp.left != null) {
    queue.offer(temp.left);
  }
  if (temp.right != null) {
    queue.offer(temp.right);
  }
}


// o/p : 1,2,3,4,5

This code performs a level-order traversal of the binary tree using a queue. It starts from the root node and adds it to the queue. Then, it repeatedly dequeues nodes from the queue, prints their data, and enqueues their left and right children if they exist. This process continues until all nodes in the tree have been visited.

Bonus: Binary Search in Java

Binary search in Java is a searching algorithm commonly applied to arrays or lists. It is used to find the position of a target value within a sorted array or list.

Binary trees, on the other hand, are a data structure consisting of nodes in a hierarchy, where each node has at most two children, referred to as the left and right child. Binary search trees (BSTs) are a specific type of binary tree where the values are stored in a sorted order, and each node’s value is greater than all values in its left subtree and less than all values in its right subtree.

While binary search and binary trees share the term “binary,” they are distinct concepts and are not directly related in terms of implementation. However, binary search trees leverage the principles of binary search to efficiently search, insert, and delete elements. The property of binary search trees ensures that searching for a value can be performed efficiently, similar to binary search in sorted arrays.

Here’s the explanation and execution of the binary search algorithm in Java

int low = 0;
int high = nums.length - 1;
while(low <= high) {
  int mid = (high + low) / 2;
  if(nums[mid] == key) {
    return mid;
  }

  if(key < nums[mid]) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
return -1;

In binary search, we look into the array until the low index becomes greater than the high index. We iterate until this condition holds true.

First, we find the mid index of the array using the formula (high + low) / 2.