Constructing Binary Tree from given Preorder and Inorder Traversal.

Let us consider the following traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F


In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.


                                                                       A
                                                                       /\
                                                                      /  \
                                                            D B E    F C


We recursively follow above steps and get the following tree.

                                                                       
                                                                       A
                                                                       / \
                                                                      /   \
                                                                    B     C
                                                                    /\      /
                                                                   /  \    /
                                                                 D  E  F
Algorithm: buildTree()

1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

Removing Pair in a string.

Suppose we have a string "RGBBGBGR". we have to eliminate the couple (two same chars adjacent to each other) recursively.

For example
RGBBGBGR --> RGGBGR-->RBGR

This solution is O(n) with recursion.

Program code:

#include <stdio.h>

#include <conio.h>

#include <string.h>

void pair_remove(char []);

void main()

{

char a[]="RGBBGBGRRGRR";

clrscr();

pair_remove(a);

printf("%s\n", a);

getch();

}

void pair_remove(char a[])

{

int remove=0,i,j;

int len=strlen(a);

for(i=0;i<len-1;i++){

if( a[i]== a[i+1] )

{

for(j=i+2;j<=len;j++) 

{

a[i]=a[j];

i++;

remove=1;

}

}

if ( remove )

break;

}

if ( remove )

pair_remove(arr);

}

Spiral of a Matrix.

The Following code prints the matrix in a spiral manner.


Program Code:



#include<conio.h>
#include<stdio.h>
void main()
{
int m,n,i,j,left,right,top,down,len,itr;
int a[5][5];
clrscr();
printf ("enter m (max 5):  ");
scanf("%d",&m);
printf ("enter n (max 5):  ");
scanf("%d",&n);
printf ("Enter the elements of matrix one by one\n");
for (i=0;i<m;i++)
    for (j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf ("you have entered the matrix\n");
for (i=0;i<m;i++)
{   for (j=0;j<n;j++)
printf("%6d ",a[i][j]);
    printf ("\n");
}
left=0;
right=n;
top=0;
down=m;
itr=0;
len=m*n;
printf ("\n");
printf ("The spiral form is : ");
printf ("\n");
while (itr<len)
{
for (j=left;j<right;j++,itr++)
printf ("%d ",a[top][j]);
top++;


for (i=top;i<down;i++,itr++)
printf ("%d ",a[i][right-1]);
right--;


for (j=right-1;j>=left;j--,itr++)
printf ("%d ",a[down-1][j]);
down--;


for (i=down-1;i>=top;i--,itr++)
printf ("%d ",a[i][left]);
left++;
}
printf ("\n");
getch();
}

Finding the Odd repeating Number.

Given an array of positive integers. Each number in the array repeats even number of times, only 1 number repeats odd number of times. Find that number.



This Solution is O(n) Time complexity.


#include<stdio.h>
#include<conio.h>
void main()
{
int a[]={4,3,4,3,1};
int len=(sizeof(a)/sizeof(int)),n=a[0],i;
clrscr();
for(i=1;i<len;i++)
{
n^=a[i];
}
printf("%d\n",n);
getch();
}

Inheritance in C.

In C, Inheritance can be implemented through struct.


For example.


struct base
{
/* base class members */
}b;
struct derived
{
struct base super;
/* derived class members */
}d;
void main()
{
struct base *base_ptr = (struct base *)&d; // upcast
getch();
}

Swapping With Pointer.

Swap two pointers without using temporary variables?


#include<stdio.h>
#include<conio.h>
void main()
{
int i=10;
int j=20;
int *a,*b;
clrscr();
a =&i;
b=&j;
printf("Before:%d\t%d\n",*a,*b);
*a^=*b;
*b^=*a;
*a^=*b;
printf("After:%d\t%d\n",*a,*b);
getch();
}

Finiding Max.

Find the maximum of three numbers using conditional operator (ternary operator) ?



#include<stdio.h>
#include<conio.h>
void main()
{
int num1=34,num2=27,num3=61,max;
clrscr();
max=num1 > num2 ? num1 > num3 ? num1: num3: num2 >num3 ? num2: num3;
printf("%d",max);
getch();
}