A Simple C Code for Binary Tree Traversal

Three traversal methods
     i)   preorder traversal
     ii)  inorder traversal
     iii) postorder traversal

This post may seem very simple . But to solve the problems related to binary trees you should have clear understanding of these traversals . For an example ,creating mirror image of the tree depends on postorder traversal .
Consider the following tree

 Preorder  :  A B C D E F G
 Inorder   :   C B D A F E G
 Postorder : C D B F G E A

 Code :(in C)

 Preorder Traversal :

 void preorder_traversal(struct node * node)
 {
if(node!=null)
{
printf("%d ",node->data);
preorder_traversal(node->left);
preorder_traversal(node->right);
}
 }

 Inorder Traversal :

 void inorder_traversal(struct node * node)
 {
if(node!=null)
{
inorder_traversal(node->left);
printf("%d ",node->data);
inorder_traversal(node->right);
}
 }

 Postorder Traversal :

 void postorder_traversal(struct node * node)
 {
if(node!=null)
{
postorder_traversal(node->left);
postorder_traversal(node->right);
printf("%d ",node->data);
}
 }

Please let me know if there is any bug in the above code and your suggestions are always welcome .

C Program to Rotate array by k times

Lets assume you have array of n=7 elements . And if u rotate it by k=3 times the input and output will be
I/P :  1 2 3 4 5 6 7
O/P: 5 6 7 1 2 3 4

This can be done in 3 steps.

Steps are:
i) reverse the whole array  ( 7 6 5 4 3 2 1 ).
ii)reverse first k elements ( 5 6 7 4 3 2 1 ).
ii)reverse the remaining n-k elements (5 6 7 1 2 3 4).

Note : And here's the thing. You have the reverse module in common .So write it as a separate function  ( modularity ) and it can be reused ( reusability ) . And if k is greater than we don't need to rotate it k times. For an example if u rotate the array by 7 times the output will be 1 2 3 4 5 6 7 (same as input) . so if k is 9 it is equal to rotating array by 2 times.

Code : (in C) 

void rotate_array(int* array,int n,int k)
{
if(n < 1 || k < 1)
return ;
if(k > n)
k=k%n;
reverse_array(array,0,n-1);
reverse_array(array,0,k-1);
reverse_array(array,k,n-1);
}

void reverse_array(int* array,int first,int last)
{
if(first>=last)
return;
int temp;
while(first < last)
{
temp=array[first];
array[first]=array[last];
array[last]=temp;
first++;
last--;
}
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

C Program to Rotate 2D array by 90 degrees

This concept is used in rotating images .Rotating array by 180 degree is very easy .
For an example if the array is (let's assume 5x5 array)
1   2   3   4   5
6   7   8   9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

and if we rotate it by 180 degrees it will look like
21 22 23 24 25
16 17 18 19 20
11 12 13 14 15
6   7   8   9  10
1   2   3   4   5

we can acheieve it by swapping first row and last row , second row and fourth row.
But to achieve 90 degree rotation the steps are
 i) rotate array by 180 degrees first .
 ii)for every element(i,j) in 2D matrix , if i < j swap (i,j) and (j,i) .
So the output will be 90 degrees rotated
 21 16 11 6   1
 22 17 12 7   2
 23 18 13 8   3
 24 19 14 9   4
 25 20 15 10 5

 Note :Here we are doing it in place.This will work only if m and n are same. otherwise we need to create a new array of size nxm .

 Code : (in C)

  void rotate90Degrees(int **array,int m ,int n)  // mxn matrix
 {
     int i,j,rows=m-1,temp;
 
     //rotate array by 180 degrees
     for(i=0;i<=rows/2;i++)
     {
if(rows<=i)
break;
for(j=0;j < n;j++)
{
temp=array[i][j];
array[i][j]=array[rows][j];
array[rows][j]=temp;
}
rows--;
       }
 
      //swap elements to rotate array by 90 degrees
      for(i=0;i < m;i++)
     {
for(j=0;j < n;j++)
{
if(i < j)
{
temp=array[i][j];
array[i][j]=array[j][i];
array[j][i]=temp;
}
               }
       }
 }

Please let me know if there is any bug in the above code and your suggestions are always welcome .