Java program to convert a binary tree to a doubly linked list, in place

Algorithm :
The problem can be solved recursively.
1. Convert the left subtree into a doubly linked list
2. Convert the right subtree into doubly linked list
3. root.left= the rightmost node of the left subtree in the doubly linked list
4. root.right=the leftmost node of the right subtree in the doubly linked list
5 return root.
At the end of recursion, from the main routine, traverse to the leftmost node
which gives the headnode of the doubly linked list.


public TreeNode treeToDoublyLinkedList(TreeNode root)
{
// Converts a tree to doubly linked list, in place


if(root==null)
{//Stop condition for recursion
// If the tree is null, resulting DLL is also null
return null;
}

TreeNode leftsubtree=treeToDoublyLinkedList(root.left);
TreeNode rightsubtree=treeToDoublyLinkedList(root.right);

if(leftsubtree!=null)
{
 while(leftsubtree.right!=null)
  {
leftsubtree=leftsubtree.right;
   }
   leftsubtree.right=root;
}
    root.left=leftsubtree;

  
if(rightsubtree!=null)
{
 while(rightsubtree.left!=null)
  {
 rightsubtree=rightsubtree.left;
   }
   rightsubtree.left=root;
}
root.right=rightsubtree;

return root;

}

Java program to check if a Linked List is a palindrome

Algorithm:
1. Find the length of the list.
2. Reverse the list from the middle.
3.Compare the lists
4.Reverse the second half again and join back.

Java Program:

public boolean isPalindrome()
{
int len=getLength(); //gets the length of the list
int mid=(len/2)+1;
ListNode temp=headnode;
int i=1;
while(i<mid)
{
temp=temp.nextnode;
i++;
}

ListNode newlisthead=temp.nextnode;
ListNode middlenode=temp;

ListNode temp1,temp2,temp3;

temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;
newlisthead=temp2;
ListNode lastnode=newlisthead;  
// Start comparison

temp1=headnode;
temp2=newlisthead;

boolean palindrome=true;

while(temp2!=null)
{
Comparable dat1=(Comparable)temp1.data;
if(dat1.compareTo(temp2.data)!=0)
{
temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;

newlisthead=temp2;
middlenode.nextnode=newlisthead;
lastnode.nextnode=null;
return false;
}

else
{
temp1=temp1.nextnode;
temp2=temp2.nextnode;
}
}

temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;

newlisthead=temp2;
middlenode.nextnode=newlisthead;
lastnode.nextnode=null;
return true;


}

Java program to Reverse Linked List

public void reverseList()
{
ListNode temp1,temp2,temp3;

temp1=headnode;
temp2=headnode.nextnode;
temp3=null;
headnode.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;
headnode=temp2;

}

Java program to compare two binary trees

Algorithm:

   1. If roots of boths trees are null, then the trees are same (stopping condition for the recursion).
   2. If
       - the data in the roots are same &
       - the left subtrees are same &
       - the right subtrees are same
        Then the trees are same
    Else
        -trees are not same
        


public boolean compareTree(TreeNode root1,TreeNode root2)
{
if(root1==null && root2==null )
{
return true;
}

Comparable data1,data2;
data1=(Comparable)root1.data;
data2=(Comparable)root2.data;

if(data1.compareTo(data2)==0 && compareTree(root1.left,root2.left)
     && compareTree(root1.right,root2.right))
{
return true;
}
else
return false;


}

Java program for Pattern Matching

public void getMatches(String text_file_string, String match_string )
{
    int n,m;
    n=text_file_string.length();
m=match_string.length();
char[] text_file=new char[n];
text_file_string.getChars(0, n, text_file, 0);
char[] match_str=new char[m];
match_string.getChars(0, m, match_str, 0);
int cntr=0;

for (int i=0,j=0; i<=n-m;i++) {
      cntr++;
if(text_file[i]==match_str[0])


{
if (text_file[i+m-1]==match_str[m-1])
{
for(j=0;j<m;j++ )
{
cntr++;

if(text_file[i+j]!=match_str[j])
break;
}
if(j==m)
{
System.out.println("Mathc found at"+ (i+1));
i=i+m;
}
}
}


}

}

Java program to implement Hash Table

A hash table implementation in Java using separate chaining. It creates a linked list for resolving hash collision.
All keys with the same hashcode "h"  is added to the linked list stored at the index "h".
The time complexity of insertion is O(1), no matter how loaded the hash table is. Time complexity for
retrieval is O(1) when the load factor is less than 1.


package lab.hashing;

import lab.linkedlist.*;

public class HashTable
{
   final int INIT_SIZE=100;
   final int INCREMENT=100;
   int CURRENT_SIZE;
   int LOAD_FACTOR=0;
   LinkedList[] hashtable=new LinkedList[INIT_SIZE];

   public HashTable()
   {
  CURRENT_SIZE=INIT_SIZE;
   }



   public void put(Object key,Object value)
   {
  int index;
  Hashable hashkey=(Hashable)key;
  index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;
  if(hashtable[index]==null)
  {
  LinkedList seperatechain=new LinkedList();
  hashtable[index]=seperatechain;
  seperatechain.insertBegining(value);
  }
  else
  {
  hashtable[index].insertBegining(value);
  }

   }


   public Object get(Object key)
   {
  int index;
  Hashable hashkey=(Hashable)key;
  index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;

  if(hashtable[index]==null)
  {
  return null;
  }
  else
  {
  return hashtable[index].search(key);
  }
   }


}

Java program to simulate Multiple Producer Consumer Problem

The Multiple Producer Consumer Problem can be solved using the Java inter thread communication mechanism.


package lab.thread;

public class Queue {
static int n;
static boolean produced;
public Queue()
{
n=0;
produced=false;
}

synchronized public void get(int id)
{

while(!produced)
{    try{
wait();
      }catch(InterruptedException ie)
      {
     System.out.println("Caught Interrupted exception");
       }
    }
System.out.println("Got "+n +" By Consumer: "+id);
produced=false;
notifyAll();
}

synchronized public void put(int val,int id)
{
while(produced)
{
try{
wait();
}catch(InterruptedException ie)
{
System.out.println("Caught Interrupted exception");
}
      
}
n=val;
System.out.println("Put : "+n+ " By Producer: "+id);
produced=true;
notifyAll();
}


}





package lab.thread;

public class Producer extends Thread {

Queue q;
int id;
static int p=1;

public Producer(Queue qu,int sn)
{
q=qu;
id=sn;
this.start();
}

public void run()
{

while(p<100)
{
q.put(p++,id);

}
}


}





package lab.thread;

public class Consumer implements Runnable
{
Queue q;
int id;

public Consumer(Queue qu,int sn)
{
q=qu;
id=sn;
new Thread(this,"Consumer").start();
}

public void run()
{

while(true)
{
q.get(id);

}
}

}

package lab;

public class Runner 

{

 public static void main(String params[])

{

lab.thread.Queue q=new lab.thread.Queue();

new lab.thread.Producer(q,1);

new lab.thread.Consumer(q,1);

new lab.thread.Producer(q,2);

new lab.thread.Consumer(q,2);

new lab.thread.Consumer(q,3);

}

}