Check whether a given tree is symmetric with structure wise or not

How will you check whether a given tree is symmetric with structure wise or not.

Ex:
Symmetric (structure wise)
            5
          /   \
         3    9
         \   /
         4  8

 Not symmetric

            5
          /   \
         5     9
        /      /
       3     8

Implementation

class CheckForSymmetricTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

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

//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}
}

public static boolean isSymmetric(Tree root){
if(root == null)
return true;

return isSymmetric(root.left, root.right);
}

public static boolean isSymmetric(Tree r1, Tree r2){
if(r1==null && r2==null)
return true;

if(r1==null || r2==null)
return false;

return (isSymmetric(r1.left, r2.right) && isSymmetric(r1.right, r2.left));
}

public static void main(String []args){
int []a = {1,2,3,4,5,6,7};

Tree root = Tree.createBST(a, 0, a.length - 1);

boolean result = isSymmetric(root);

if(result)
System.out.println("Given tree is a symmetric tree");
else
System.out.println("Given tree isn't a symmetric tree");
}

}

Output : Given tree is a symmetric tree

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Method 1: (By using sorting)

        void arrange(int []array){
                if(array == null || array.length == 0)
                     return;
java.util.Arrays.sort(a);
}

Time Complexity : O(NlogN)

Method 2: (by counting the 0s, 1s and 2s)

       void arrange(int []array){
                if(array == null || array.length == 0)
                      return;

int countZeros = 0;
int countOnes = 0;
int countTwos = 0;

for(int i = 0; i < a.length; i++){
if(a[i] == 0)
countZeros++;   //count number of  zero
else if(a[i] == 1)
countOnes++;    //count number of  one
else if(a[i] == 2)
countTwos++;    // count number of two
}

for(int i = 0; i < countZeros; i++)
a[i] = 0;          //write zero to array

for(int i = countZeros; i <a.length-countTwos; i++)
a[i] = 1;          //write one

for(int i = countZeros+countOnes; i < a.length; i++)
a[i] = 2;          //write two
}

Time Complexity : O(N)

Method 3 : (By using Dutch flag algorithm)
     For Dutch Flag Algorithm, click here

      void arrange(int []a){
                if(array == null || array.length == 0)
                      return;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

//Traverse the array once to pickup min and max values
for(int i = 0; i < a.length; i++){
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}

int p = 0, q = a.length - 1;
int temp;  //for swapping values

for(int i = 0; i < q; i++){
if(a[i] == min){   //place the min value at the lowest position
temp = a[p];
a[p] = a[i];
a[i] = temp;
p++;
}
if(a[i] == max){   //place the max value at the highest position
temp = a[q];
a[q] = a[i];
a[i] = temp;
q--;
i--;
}
}
}

Time Complexity : O(N)

Segregate Even And Odd Numbers in given array

Given an array A[], write a function that segregates even and odd numbers. The functions should put all even numbers first, and then odd numbers.

Example
  Input = {12, 34, 45, 9, 8, 90, 3}
  Output = {12, 34, 8, 90, 45, 9, 3}

  In the output, order of numbers can be changed, i.e., in the above example 34 can come before 12 and 3 can come before 9.

Algorithm 
segregateEvenOdd(int []array)
     1) Initialize two index variables left and right:
            left = 0,  right = size -1
     2) Increment left index until we see an odd number.
     3) Decrement right index until we see an even number.
     4) If left < right then swap arr[left] and arr[right].

Implementation

class SegregateEvenAndOddNumbers{
 
    static void segregate(int []a){
        if(a == null || a.length == 0)
            return;
        
        int left = 0, right = a.length - 1;
        while(left < right){
            
            while(a[left]%2 == 0 && left < right)
                left++;
            
            while(a[right]%2 != 0 && left < right)
                right--;
            
            if(left < right){
                swap(a, left, right);
                left++;
                right--;
            }
        }
    }
   
     //Utility function to swap array elements
    static void swap(int []a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
 
    public static void main(String []ar){
        int []a = {12, 34, 45, 9, 8, 90, 3};
        segregate(a);
        System.out.println("\nafter the shuffling" + java.util.Arrays.toString(a));
    }
}

Find Minimum Number Of Swap Required To Sort Input Array

Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array.

Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.

Implementation

int swapRequired(int []array){
       //Boundary condition
       if(array == null || array.length == 0)
             return 0;

       int swap = 0, count = 0;
        //iterate over all the elements of given array
       for(int i = array.length; i >= 0; i--){
               if(array[i] == 0)
                    count++;            //count the number of 0s between two 1s
               else
                    swap += count;
       }
       return swap;   //return the count of required swap
}

Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort.

The algorithm works as follows:
1) Find the minimum value in the list.
2) Swap it with the value in the first position.
3) Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

Ex: Given array : 64 25 12 22 11
  After first step : 11 25 12 22 64
   After Second Step : 11 12 25 22 64
  After third step : 11 12 22 25 64
  After fourth step : 11 12 22 25 64

Implementation

class SelectionSort{
//method for selection sort
public static void selectionSort(int []a,int size){
int min;

for(int i = 0; i < size-1; i++){
min = i;
for(int j = i+1; j < size; j++){
if(a[min] > a[j]){
min = j;   //find the index of minimum value
}
}
if(min != i)
swap(a, i, min);
}
}

//Utility function to swap the elements in array
public static void swap(int []a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};

selectionSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Insertion Sort

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

Example: The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}.
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9

Key points:
   1) Simple implementation
   2) Efficient for (quite) small data sets
   3) Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n +          d), where d is the number of inversions
   4)More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort        or bubble sort; the best case (nearly sorted input) is O(n)
   5)Stable; i.e., does not change the relative order of elements with equal keys
   6)In-place; i.e., only requires a constant amount O(1) of additional memory space
   7)Online; i.e., can sort a list as it receives it

class InsertionSort{
//method for insertion sort
public static void insertionSort(int []a, int size){
int temp;

for(int i = 1; i<size; i++){
for(int j = i; j > 0; j--){
if(a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};
insertionSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Time Complexity  : O(N^2) worst and average case
Space Complexity : O(1)

Bubble Sort

Algorithm :
Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

After first pass, largest element will be at the end of the array.

Ex:
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared. Three passes will be required.
First Pass:
( 5 1 4 2 8 )  ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 )  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 )  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 )  ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 )  ( 1 4 2 5 8 )
( 1 4 2 5 8 )  ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )

Implementation:

class BubbleSort{
//method for the bubble sort
public static void bubbleSort(int a[], int size){
int temp = 0;
for(int i = 0; i < size-1; i++){
for(int j = 0; j < size-i-1; j++){
if(a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};

bubbleSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}