Monthly Archives: October 2013

Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely

  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.

For example consider the simple  3 node binary tree

In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it’s traversal sequences for the three algorithms.

In-order: 1  2  3  4  5  6  7  8

Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it’s elements.

Here is the C++ code for all the traversals.

Finding the height of the binary tree

Given a binary tree how to find the height of the tree. 
It is defined as the number of nodes in the longest path from root to any leaf.

 We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the below tree has a height of 4.

We can calculate the height of the tree using recursive method very easily. It is based on the observation that height of a binary tree is 
1 + Max( height(left-sub-tree), height(right-sub-tree) )
Here is the C++ code which implements this simple algorithm.

Subset sum problem

Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value.

For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t have any subset with sum 100.

A simple recursive solution can be given as follows. We pass the array, the starting index, and target sum to the function. 
At each index we have two choices:
  • Include the current element and search for {sum – current_num} in the remaining set of elements.
  • Exclude the current element and search for sum in the remaining set of elements.
public static boolean hasSum(int [] array, int start, int sum)
{
if( sum == 0 ) //found the sum?
return true;

if( start > array.length-1 )//reached end of the array?
return false;

return hasSum(array, start+1, sum) || hasSum(array, start+1, sum-array[start]);

}

But this algorithm has an exponential time complexity which is not efficient. 
Let us look at more efficient approach based on Dynamic programming.
We take a boolean matrix of size (sum+1) x (N+1) where sum is the target sum and N is the size of the given set.
matrix[i][j] = true; indicates that there is a subset of array[0..j-1] which contains the sum i.
We initialize the following entries as base values.
  • matrix[0][j] = true; where 1 <= j <= N since in any set there will be empty subset with sum 0;
  • matrix[i][0] = false; where 1 <= i <= sum since we can’t find a sum > 0 in an empty array.
We calculate the remaining entries as follows.
matrix[i][j] = matrix[i][j-1];
If there exists a subset of array[0..j-2] with the sum i; then there should be a subset of array[0..j-1]also with the sum i.

If i >= array[j-1]; we check to see if matrix[i – array[j-1]][j-1] is true. This means check if there is any subset of array[0..j-2] with sum i-array[j-1].
If there is, then we assign true to this entry.

Finally we return the value at matrix[sum][N] which indicates true if there is a subset of array[0..N-1] with the given sum. Otherwise false.

Here is the Java code which implements this.


Jolly jumpers problem

In this post I introduce you to a competitive programming problem called Jolly jumpers. This problem is available on UVa online judge on this link

UVa site is one of the first online judge websites which listed programming problems from different competitions like ACM ICPC and IOI and allowed users to solve and submit their programs online to check if their solutions are correct or not. This site contains a huge number of programming problems of varying complexities. Go and register yourself on this site if you are passionate about programming and start solving the problems!

The problem is defined as follows…


A sequence of n > 0 integers is called a jolly jumperif the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,
1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.

Output

For each line of input, generate a line of output saying “Jolly” or “Not jolly”.

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

The C++ code to solve this problem is given below.
To solve this problem we use a diff array. We try to calculate the absolute difference between each of the successive elements and populate the result in the diff array. while populating, we check if the result lies in the range [1, N-1]. If not, the array is not a jolly jumper. Also if the same difference appears more than once, it is not a jolly jumper.

Finding three elements with zero sum in an array.

Given an array of positive and negative numbers, how do we write a program to check if it has three elements with sum 0.

For example, the array  {-31, 19, -6, -45, 12, -8, 3, -77, 56, 29} contains {-31,12,19} with sum zero.

One obvious solution is to examine each possible triplet of the array and check if there is a triplet with sum = 0. But this takes O(n3) time and is not efficient for large arrays.

A better approach would be to sort the array first in increasing order. Follow this iterative algorithm.

  • Fix the first element, start two pointers one at the begin and the other at the end of the sorted array. 
  • If the sum of the three elements is zero return.
  • If the sum is greater than zero, we decrement the end pointer so that the sum moves closer to zero
  • If the sum is negative, we increment the begin pointer to add up value to sum.
  • Iterate this procedure until the fixed element moves towards the end.

This procedure takes O(n log n) for sorting the array and O(n2) for actually finding the triplet. So the overall time complexity would be O(n2) and O(1) extra space. 

Here is the java code to do this.



How to insert into a binary search tree

A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture.

This is an example of binary search tree. The node at the top containing 5 is the root and all the elements to the left of it(left sub-tree) are less than 5 and all the elements to the right of it (right sub-tree) are greater than 5. A binary search tree does not allow duplicate elements in it. 
In this post we see how an insertion method works. It works very similar to the binary search.

The insert method looks at the root. If the given data is lesser than root data, it has to be inserted into the left sub-tree. Otherwise it has to be added in the right sub-tree. Since the left/right sub-trees are also binary search trees, we call the procedure recursively.
Here is the complete C++ program which implements a binary search tree in Object Oriented approach. I have used in-order traversal to print all the elements of the binary search tree. These procedures are explained in future posts.

Deleting duplicates from a sorted linked list

Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list
1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5
The output should be
1 -> 2 -> 3 -> 4 ->5

To solve this problem we take two pointers current and next, we iterate through the list until the next pointer reaches the end of the list.

In each iteration we compare the data at current and next nodes. If they are equal, we delete the next node, and the next pointer is advanced to the subsequent node. Take a look at the pictorial representation of this step to understand better.


Here is the working code of C++ for this.

Sorting a linked list using bubble sort

How do we sort a linked list? 
In this post, we see one such method using bubble sort algorithm.

We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

Here is the Object Oriented C++ implementation. 
 

Searching for an element in the sorted matrix

Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?

Example of the array can be

int[][] matrix = {
                   {1,3,5,7,9},
                   {10,12,14,16,18},
                   {19,21,23,25,27},
                   {28,30,32,34,36},
                   {37,39,41,43,45}
                };

This can be done using the following algorithm. 

We start our search with the top right element. 

  • If it is equal to the key, we print corresponding indices and we are done!. 
  • If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser. 
  • If the key is less than the given element, we move to the previous column.  The reason is similar to the above.

We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.

Printing biggest elements to its right in an array

Given array of elements we have to write a program to print the biggest element to it’s right for each of the elements in the given array.

For example let us consider the array {3, 9, 2, 4, 6, 1}.

The output for this array should be {9, 6, 6, 6, 1, -1}. As a convention, we print -1 for the last element because there are no elements to it’s right.

This problem can be solved in O(n) time and O(1) space by using the following algorithm.

Start from the end of the array. print -1 for the last element. Use a variable to keep track of the greatest element found so far while traversing backwards and fill the entries with this variable.

Here is the Java program to do this.