Wednesday, May 13, 2015

How does a radix sort work?

Radix sort is an integer sorting algorithm. As it's name indicates, it sorts a list of numbers based on the digits of the numbers. 

It's a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.

Let us understand this algorithm using an example. 
Consider the array [235, 10, 784, 69, 51]

We first sort the numbers based on the least significant digit, i.e the digit at 1's place. It becomes [10, 51, 784, 235, 69]. Observe that the these numbers are now sorted according to it's last digit ([0,1,4,5,9]).

Next we consider the digits at 10's place and sort them. It transforms to
[10, 235, 51, 69, 784]. These are sorted according to the last but one digits ([1,3,5,6,8])

Similarly in the next step it becomes [10, 51, 69, 235, 784]

Now the entire array is sorted! We no longer need to sort array because we have at most 3 digits in any number.

Implementation details:
Suppose there are at most D digits in any number, we call the counting sort D times for each place.

Let us briefly know how counting sort works. For more details, you can check my previous post.

It first groups the numbers into buckets. The result of this is a count array of size 10 (assuming the numbers are in the range 0-9). 

Calculate the prefix array of this, we get the sorted positions of given numbers.

Then we use a temporary array to arrange the numbers in sorted order.

An alternative implementation could be to maintain a list of numbers for each bucket, and merging them to a sorted array. But this approach takes extra memory for the list of buckets.

The following code shows  the implementation of the above algorithm.
Exercise: Try to solve this SPOJ problem using radix sort.

Saturday, May 9, 2015

Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. 

A binary tree is called a symmetric tree if it's left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

    1
   / \ Symmetric
  2   2  
    1
   / \ Asymmetric
  2   3 
      1
     / \
    2   2  Symmetric
   /     \
  3       3

We can design a recursive algorithm like the following.
  1. An empty tree is a symmetric tree.
  2. At each node we check the following
    1. If the left value and right value are same
    2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
    3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
  3. If all the above conditions are satisfied then the tree is symmetric.
Here is the C++ implementation of this.

Friday, May 1, 2015

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  /  \
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.