This algorithm is designed to take in a binary tree (not necessarily a BST/Binary Search Tree) and reverse the nodes at each level to generate the mirror image of that binary tree.

How Does it Work?

The mirror image of a binary tree is simply the result of reversing the nodes at every level. So, the trick is to recursively visit every node, starting with the root and going to its left and right sub-trees. For every node visited, including the root itself, you just swap the left and right sub-trees. When there are no nodes left (i.e. the left and right sub-trees of the current node are null), then the algorithm returns.

Sample Implementation

Here is a sample implementation of the algorithm. It is fully working code, so you may double click on it and copy the whole example into your preferred IDE to test it and debug it for better understanding. Sample output is provided below the sample.

 //Algorithm to get the mirror image of a binary tree and
 //print out the before and after images.
 public class MirrorTree {

     private static class Node {
         public int value;
         public Node left;
         public Node right;
         public Node(int value) { this.value = value; }
     }

     //Example of algorithm being used.
     public static void main(String[] args) {

         //Create a tree on which to run the mirror algorithm.
         Node root = new Node(1);
         root.left = new Node(2);
         root.left.left = new Node(3);
         root.left.right = new Node (4);
         root.right = new Node(5);
         root.right.right = new Node(6);
         root.right.right.right = new Node(7);

         //Print out the original tree.
         System.out.println("Tree before mirror:");
         printTree(root);

         //Run the mirror algorithm.
         mirror(root);

         //Print out the resulting tree.
         System.out.println("\nTree after mirror:");
         printTree(root);
     }

     //The mirror algorithm itself.
     public static void mirror(Node root) {

         //Terminate when the root is null.
         if (root == null) return;

         //Swap the left and right subtrees.
         Node tmp = root.left;
         root.left = root.right;
         root.right = tmp;

         //Recursively repeat on left and right subtrees.
         mirror(root.left);
         mirror(root.right);
     }

     //Utility function to print the binary tree as an example.
     public static void printTree(Node root) {
         if (root == null) return;
         printTree(root, 0);
     }

     //Private utility function for formatting the tree display.
     private static void printTree(Node root, int level) {
         if (root == null) return;
         printTree(root.left, level + 1);
         for (int i = 0; i < level; ++i) System.out.print("  ");
         System.out.print(root.value + "\n");
         printTree(root.right, level + 1);
     }
 }

Output From Example

This is an admittedly lazy way of printing a binary tree, but if you look at it as if the left side of your screen is the top of the screen, it gets the job done. You can see that that every node in this tree is displaying the mirror image of its original in the second printout.

 Tree before mirror:
     3
   2
     4
 1
   5
     6
       7
 
 Tree after mirror:
       7
     6
   5
 1
     4
   2
     3

This is a standard implementation of the merge-sort algorithm. It is heavily commented to help you understand it.

Merge-sort is a divide and conquer based algorithm with a very simple premise.  It keeps dividing the provided data set in half until only 1 element remains in each recursive call.  Then it merges the sorted sub-sections of the array on the way back up.

1. Take an array as input.
2. Recursively divide the array in half and merge sort each half (so, one recursive call in each invocation for the left half of the array, and one for the right half).
3. When just one element remains, return that element.
4. After the recursive calls, sort the two halves.  Following the recursive logic, each half will already be sorted in itself.  So, the merge just requires repeatedly taking the next smallest element from either of the halves until both are empty.

 import java.util.Arrays;

 public class MergeSort {

     public static void main(String[] args) {
         int[] arr1 = {1,7,2,9,3,5,2,3,4,7,8,9,6,1,3};
         int[] arr2 = {1,7,2,9,3,5,2,3,4,7,8,9,6,1,3};
         System.out.println("Starting array (unosrted)");
         System.out.println(Arrays.toString(arr1));
         mergeSort(arr1);
         System.out.println("Personal mergesort result:");
         System.out.println(Arrays.toString(arr1));
         Arrays.sort(arr2);
         System.out.println("Built in sort result:");
         System.out.println(Arrays.toString(arr2));

     }

     public static void mergeSort(int[] a) {
         mergeSort(a, new int[a.length], 0, a.length - 1);
     }

     private static void mergeSort(int[] array, int[] buffer,
             int start, int end) {

         //Continue until start is equal to end (i.e. there is only
        //one element left.
         if (start < end) {

             //Calculate the midpoint.
             int mid = (start + end) >>> 1;

             //Recurse and sort the lower and upper halves of the
             //array.
             mergeSort(array, buffer, start, mid);
             mergeSort(array, buffer, mid + 1, end);

             //Merge the resulting arrays together.
             merge(array, buffer, start, mid, end);
         }
     }

     private static void merge(int[] array, int[] buffer, int start,
            int mid, int end) {

         //Copy the full range of elements from the array to the
        //temporary buffer.
         for (int i = start; i <= end; ++i) buffer[i] = array[i];

         int low = start;
         int high = mid + 1;
         int curr = start;

         //While there are still low-half and high-half elements to
        //compare, take the smaller one and add it to the real
        //array from the helper buffer.  Must track lower array
        //index, upper array index, and real array index. Also must
        //remember that this ends when we get to the end of either
        //half of the array.
         while (low <= mid && high <= end) {
             if (buffer[low] <= buffer[high])
                array[curr++] = buffer[low++];
             else 
                array[curr++] = buffer[high++];
         }

         //We got to the end of one of the halves first.  If it was
        //the bottom half, then the upper half is already in the
        //correct position which is fine.  If we got to the end of
        //the upper half first then we need to copy the bottom
        //half's remainder to the end.
         while (low <= mid) {
             array[curr++] = buffer[low++];
         }
     }
 }

The quick-sort algorithm (AKA partition exchange sort) is one of the fastest known in-memory sorting algorithms in practice, though its worst-case timing is actually worse than merge-sort. The algorithm is interesting from an academic point of view, but in real applications, sorting isn’t a massive problem until data sets become too large to sort on a single node. Quick sort typically isn’t used once this occurs.

How Does it Work?

Quick sort works by finding a pivot point (the middle element in this case for ease), moving all elements less than the pivot element to the left of it, and all elements greater than the pivot to the right of it, then recursing to do the same thing to the left half of the array and the right half of the array. This continues until only one element is left at the given level. By this point, the whole array is element sorted.

Execution Time and Characteristics

Quick sort is a n * lg(n), non-stable sorting algorithm in its average case, which makes it relatively fast. It actually outperforms mergesort in the average case, which is also n * lg(n). The problem with quick sort is that its worst-case running time is actually n^2, and while this performance is rare, it is unacceptable in many applications. Also, unstable sorts can cause problems in some applications which also leads to merge-sort being favored in many language libraries (e.g. Java Collections.sort()).

Sample Implementation

Here is a sample implementation of the Quick Sort algorithm which is heavily commented to aid in helping you to understand what it is doing. It is a full implementation, so feel free to double-click and copy the whole thing to an IDE so that you can watch it work through a debugger to aid your learning process.

 import java.util.Arrays;

 public class QuickSort {

     //Sample main method for testing the algorithm.
     public static void main(String[] args) {
         int a[] = { 9, 2, 8, 7, 1, 9, 6, 4, 2, 5, 9 };
         System.out.println("Before sorting:" + Arrays.toString(a));
         QuickSort sorter = new QuickSort();
         sorter.sort(a);
         System.out.println("After sorting:" + Arrays.toString(a));
     }

     //The array to be sorted.
     private int[] a;

     public QuickSort() {
         //Nothing to do.
     }

     //Verify array contents and call the underlying sort function.
     //TODO: Avoid storing array locally to make this thread-safe.
     public void sort(int[] a) {
         if (a == null || a.size() >> 1];
         int i = start;
         int j = end;

         //Process the given range of the array, moving i right and
         //j left until i is greater than j.
         while (i <= j) {

             //Advance i until it is not less than the pivot value.
             while (a[i]  pivot) --j;   

             //If i hasn't moved past j, swap the i value
             //(>= pivot on left) for the j value
             //(<= pivot on the right).  This allows us to
             //swap the high values on the left for the low values
             //on the right which sorts the array.
             if (i <= j) swap(i++, j--);
         }

         //Recurse to the left and right lists if there is work to
         //do in either. We moved i from the left and j from the
         //right until j was before i. So, the sub-lists that we 
         //will recurse to are start through j, and i through end.
         if (start  i) quickSort(i, end);
     }

     private void swap(int i, int j) {
         int tmp = a[i];
         a[i] = a[j];
         a[j] = tmp;
     }
 }

The purpose of this algorithm is to reverse a given string. It achieves this by advancing from the start of the string to the midpoint (or one before it) and swapping the current character with the one an equally distant from the end of the string. The string is treated as an array of characters during this process, and that array is converted back into a string when returned.

public class ReverseString {

     //Reverse the provided string.
    public static String reverse(String input) {

        //Turn the string into an array of characters so we don't
        //keep rebuilding immutable strings as we reverse the
        //contents.
        char[] chars = input.toCharArray();

        //Advance from the beginning to the middle of the array.
        //Swap the current index (l) from the left side of the
        //array with the one equally distant from the end of the
        //right side (r).
        for (int l = 0; l < chars.length / 2; ++l) {
            int r = chars.length - 1 - l;
            swap(chars, l, r);
        }

        //Turn the array back into a string and return it.
        return new String(chars);
    }

    private static void swap(char[] a, int l, int r) {
        char c = a[r];
        a[r] = a[l];
        a[l] = c;
    }

    public static void main(String[] args) {
        //Test with even and odd number of characters.
        System.out.println(reverse("Hello World!"));
        System.out.println(reverse("Hello World"));
    }
}

This example demonstrates how to use wait() and notify() in order to safely publish objects from one thread to another using blocking semantics. In real applications you should use higher level threading constructs, but understanding these lower level mechanisms is useful, especially if you ever need to implement your own higher level classes.

The DropBox Class

The key class in this program is the DropBox class which can be seen below. This class provides put() and take() functions which are implemented with blocking semantics. These blocking semantics are achieved using the wait() and notifyAll() functions which will be described later.

public class DropBox {

    private int value;
    private boolean empty;

    public DropBox() {
        value = -1;
        empty = true;
    }

    public synchronized void put(int value) {
        while (!empty) {
            try { wait(); }
            catch(InterruptedException ex) {}
        }
        empty = false;
        this.value = value;
        notifyAll();
    }

    public synchronized int take() {
        while (empty) {
            try { wait(); }
            catch(InterruptedException ex) {}
        }
        empty = true;
        notifyAll();
        return value;
    }
}

Guarded Blocks

Both put() and take() work in similar manners. They both start with what is known as a guarded block. In their guarded block, they poll a condition, in this case the empty variable, to see if it is okay to proceed with their work. If, it is not okay to proceed (like when the drop box is empty and we’re trying to take an element) then the wait() function is called. The guarded block is in a while loop as it is good practice to retest the condition being waited on after the wait is terminated. The functions that end the wait() call may be signalling any event, not necessarily the one that we were waiting for in this particular thread. So, the while loop ensures we immediately start waiting again if our desired event has not yet occurred.

The wait() and notifyAll() Functions

In most cases, you will use higher level threading mechanisms to achieve what we’re doing here with wait() and notifyAll(). But most of these higher level mechanisms are built on these lower level ones, so it is good to understand them. There are a few things you should know about these functions:

• The wait() function blocks on the intrinsic monitor lock associated with “this” object.
• That lock must be owned by the current thread in order for wait() to be called. That is the reason these functions are “synchronized”.
• It will block forever after it is called.
• The wait() block will be broken when another thread calls notifyAll() or notify() on “this” object
• Once wait() begins blocking, it yields “this” object’s monitor lock so other threads can use it. Those threads in turn must own the lock in order to call notifyAll() or notify() to wake this thread up.
• The notifyAll() function is typically used as the notify() method only signals one thread, and you cannot choose which thread that is. The notify() function is generally only useful in massively parallel applications when you don’t care which of a large number of threads does the work.

The Producer Class

The producer class is very simple since the DropBox class did most of the groundwork for us. It receives a reference to the DropBox it will use upon construction. It then implements Runnable and overrides the run() method. It uses the run method to loop 50 times, and on each loop it calls put(x) on the drop box, which does a blocking add of the next integer value. It then sleeps for 250ms just to make the application output easier to follow.

public class Producer implements Runnable {

    private final DropBox next;

    public Producer(DropBox next) {
        this.next = next;
    }

    @Override
    public void run() {
        for (int i = 0; i < 50; ++i) {
            next.put(i + 1);
            try { Thread.sleep(250); }
            catch (InterruptedException e) {}
        }
    }
}

The Consumer Class

The consumer class works just like the producer class, but in reverse. It simply implements runnable and does a blocking take() on the DropBox 50 times in a row before running to completion.

public class Consumer implements Runnable {

    private final DropBox next;

    public Consumer(DropBox dropBox) {
        this.next = dropBox;
    }

    @Override
    public void run() {
        for (int i = 0; i < 50; ++i) {
            System.out.println(next.take());
        }
    }
}

Running the Program

The following class creates a DropBox and then creates a Producer and a Consumer instance which both share that DropBox. Next, it creates two new threads, passing the Producer and Consumer Runnables to them. Finally, it starts both threads and joins on them in order to wait for them to complete before shutting down the application. Running this program will result in the Consumer printing the numbers 1-50, one line at a time. Once 50 is reached, both threads run to completion, and the join() calls finish blocking, allowing the application to terminate successfully.

public class ProducerConsumerSample {
    public static void main(String[] args) {
        DropBox dropBox = new DropBox();
        Consumer c = new Consumer(dropBox);
        Producer p = new Producer(dropBox);
        Thread t1 = new Thread(c);
        Thread t2 = new Thread(p);
        t1.start();
        t2.start();
        try {
            t1.join();
            t2.join();
        }
        catch (Exception ex) {
            System.err.println("Error joining thread.");
        }
   }
}