This is a basic algorithm for determining whether or not a binary tree is balanced.

How it Works

This algorithm builds on the Binary Tree Depth problem, and is just slightly more complex. From the referenced tree depth problem, the depth of a binary tree is equal to the level of its deepest node.

A binary tree is considered balanced if at any level, the left sub-tree is balanced, and the right sub-tree is balanced, and the difference between the height of the left sub-tree and right sub-tree is no more than 1. For this to make more sense, consider that every node in a binary tree is actually a smaller binary tree. At its simplest case, a leaf is a tree of size 1, and it is balanced because the depth of its left and right sub-trees is equal (0). So, if we ever find a sub-tree (non-leaf) where there is depth 2 on the left and 0 on the right, or vice-versa, that sub-tree is not balanced, and thus the entire tree is not balanced. In essence, we’re just recursively making sure that the depth of the sub-trees at any level varies by no more than 1.

Sample Implementation

Here is a sample implementation. You may double-click to copy the contents of the sample into your IDE so that you may play with it in a debugger to learn more.

public class BinaryTree {

     //A simple class ot represent a node in the binary tree.
     private static class Node {
         public Node(int v) { this.value = v; }
         int value;
         Node left;
         Node right;
     }

     //This main method demonstrates the isBalanced function.
     public static void main(String[] args) {

         //Create a tree where the largest depth is 5 on the left.
         Node root = new Node(5);
         root.left = new Node(3);
         root.left.right = new Node(4);
         root.left.left = new Node(2);
         root.left.left.left = new Node(1);

         //We'll give the right side maximum depth 3.
         root.right = new Node(7);
         root.right.left = new Node(6);
         root.right.right = new Node(8);
         root.right.right = new Node(9);

         //Check if the tree is balanced (it is).
         System.out.println(isBalanced(root));

         //Unbalance the tree and recheck (will fail).
         root.left.left.left.left = new Node(0);
         System.out.println(isBalanced(root));
     }

     //Determine if the given tree is balanced by recursively
     //checking if each subtree is balanced, and if the depth
     //of the subtrees varies by no more than 1.
     public static boolean isBalanced(Node root) {

         //A null tree is considered balanced.
         if (root == null) return true;

         return
             //The depth difference between the  left and right
             //subtrees is no more than 1.
             (Math.abs(depth(root.left) - depth(root.right)) < 2)

             //and both subtrees are balanced.
             && isBalanced(root.left) && isBalanced(root.right);
     }

     //This a recursive function for finding the depth of a tree.
     //The trick here is that as we recurse down to the next level
     //of the tree in each case, we add 1 to the depth.  We also
     //make sure that we only track the maximum depth between the
     //two subtrees as that is all we care about.
     public static int depth(Node root) {
         if (root == null) return 0;
         return 1 + Math.max(depth(root.left), depth(root.right));
     }
 }

Output of Example

This example simply outputs “true \n false” as the tree is balanced in the first check, and it is not balanced in the second check.

This is a basic algorithm for finding the depth of a binary tree.

How it Works

The depth of a binary tree is defined as being the level of its deepest node. So, for example, a tree that is just a root has depth = 1. A tree whose root has a left node and a right node has depth = 2 as either node is just one from the root. A tree whose root has a left node, that also has its own left node has depth = 3, and so on. Only the deepest path is relevant in determining the tree depth.

The algorithm that we use to get the depth is very concise. All it does is recursively traverse the tree while tracking the count at each level. The result of each level is the maximum depth (count) between the left and right sub-trees. So, at the root, we start with count = 1 + max(count(left-subtree), count(right-subtree)). We continue this, adding one at each level, until we get to the leaf nodes where we get the final counts. Since we only retain the maximum count at each level, by the time the original call at which started with the root node returns, we have only the maximum count (depth) of the tree left.

Sample Implementation

Here is a sample implementation. You may double-click to copy the contents of the sample into your IDE so that you may play with it in a debugger to learn more.

 public class BinaryTreeDepth {

     //A simple class to represent a node in the binary tree.
     private static class Node {
         public Node(int v) { this.value = v; }
         int value;
         Node left;
         Node right;
     }

     //This main method demonstrates the algorithm's use.
     public static void main(String[] args) {

         //Create a tree where the largest depth is 5 on the left.
         Node root = new Node(5);
         root.left = new Node(3);
         root.left.right = new Node(4);
         root.left.left = new Node(2);
         root.left.left.left = new Node(1);
         root.left.left.left.left = new Node(0);

         //We'll give the right side maximum depth 3.
         root.right = new Node(7);
         root.right.left = new Node(6);
         root.right.right = new Node(8);
         root.right.right = new Node(9);

         //Print the depth of the tree.
         System.out.println(depth(root));
         System.out.println(isBalanced(root));
     }

     //This a recursive function for finding the depth of a tree.
     //The trick here is that as we recurse down to the next level
     //of the tree in each case, we add 1 to the depth.  We also
     //make sure that we only track the maximum depth between the
     //two subtrees as that is all we care about.
     public static int depth(Node root) {
         if (root == null) return 0;
         return 1 + Math.max(depth(root.left), depth(root.right));
     }
 }

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;
     }
 }