Program to connect nodes at the same level in the tree

For eg. We are given the tree in the figure(a) and we need to connect the tree node as shown in the figure (b)

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
struct Tree *nextright;
}*root=NULL;
void displaytree(struct Tree *);
void conASL(struct Tree *);
int main()
{
struct Tree *temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
root =temp;
root->key=2;
root->nextright=NULL;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=6;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->right=temp;
conASL(root);
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
if(node->nextright==NULL)
printf("nextright=NULL");
else
printf("nextright=%d",node->nextright->key);
displaytree(node->left);
displaytree(node->right);
}
void conASL(struct Tree *node)
{
    if((node->left==NULL)&&(node->right==NULL))
        return;
    else
    {
        node->left->nextright=node->right;
        if(node->nextright==NULL)
        {
            node->right->nextright=NULL;
        }
        else
        {
        node->right->nextright=node->nextright->left;
        }
   conASL(node->left);
   conASL(node->right);
    }

}

Output:

Program to implement tree using linked list in C 

We will be using the linked list to connect the different nodes of the tree recursively and using preorder traversal to print the vertices of the tree

The sample tree used is :

The above figure shows the binary tree, however build any tree using the approach laid out in the program 

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
}*root=NULL;
void displaytree(struct Tree *);
int main()
{
struct Tree *temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=5;
root=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=6;
root->left=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
root->right=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
root->left->left=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=9;
temp->left=NULL;
temp->right=NULL;
root->left->right=temp;
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
displaytree(node->left);
displaytree(node->right);
}

Output:

Write a program to find length of Longest Common Subsequence(LCS) in two strings using dynamic programming.

#include<stdio.h>
#include<string.h>
void lcs(char*, char*, int, int);
int smax(int, int);
int array[51][51];
int main()
{
char a[50],b[50];
int m,n;
printf("Enter the first sequence \n");
scanf("%s",a);
m=strlen(a);
printf("Enter the second one\n");
scanf("%s",b);
n=strlen(b);
lcs(a,b,m,n);
printf("%d",array[m][n]);
    return 0;
}
void lcs(char *a, char *b,int m , int n)
{
    int i,j;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==0||j==0)
                array[i][j]=0;
                else if(a[i-1]==b[j-1])
                {
                    array[i][j]=1+array[i-1][j-1];
                }
                else
                {
                    array[i][j]=smax(array[i-1][j],array[i][j-1]);
                }
        }
    }
}

int smax(int a, int b)
{
    if(a>b)
        return a;
    else
        return b;

}

Output:

Write a program to find LCS (Longest common subsequence of two strings) using divide and conquer only.
First using divide and conquer only.
So , what is LCS of two strings 
Here is an eg of the same
first consider two strings a and b of lengths m and n respectively
LCS for Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Solution by Divide and Conquer

#include<stdio.h>
#include<string.h>
int lcs(char*, char*, int, int);
int smax(int, int);
int main()
{
char a[50],b[50];
int m,n;
printf("Enter the first sequence \n");
scanf("%s",a);
m=strlen(a);
printf("Enter the second one\n");
scanf("%s",b);
n=strlen(b);
printf("%d",lcs(a,b,m,n));
    return 0;
}
int lcs(char *a, char *b, int m , int n)
{
    if(m==0||n==0)
        return 0;
    else if(a[m-1]==b[n-1])
        return 1+lcs(a,b,m-1,n-1);
    else
        return smax(lcs(a,b,m-1,n),lcs(a,b,m,n-1));
}
int smax(int a,int b)
{
    if(a>b)
    return a;
    else
    return b;

}

Output:-

Calculating Fibonacci series using Dynamic Programming

Normally using divide and conquer algorithm using recurrence relation the complexity reaches to O(2^n) i.e. exponentially 
We can reduce the time the time complexity of the same by avoiding doing the necessary work and saving using reusing our previous work using dynamic programming
Here is an example of the same.
#include<stdio.h>
int sdynamicfib(int);
int table[100]={-1};
int main()
{
 int n,i,temp ;
 printf("Calculating fibonnaci series using dynamic programming\n");
 printf("Enter n");
 scanf("%d",&n);
 for(i=0;i<=n;i++)
 {
     table[i]=-1;
 }
 temp=sdynamicfib(n);
 for(i=0;i<n;i++)
 {
     printf("%d",table[i]);
     printf(" ");
 }
    return 0;
}
int sdynamicfib(int n)
{
    if(n==0||n==1)
    {
        table[n]=n;
        return n;
    }
    else
    {
      if(table[n]==-1)
      {
          if(table[n-1]==-1)
            table[n-1]=sdynamicfib(n-1);
            if(table[n-2]==-1)
            table[n-2]=sdynamicfib(n-2);
          table[n]=table[n-1]+table[n-2];
          return table[n];
      }
    }
}
 Output