Check if Binary tree is a BST

http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

BTREE Creation Search Insertion

http://www.youtube.com/watch?v=k5J9M5_IMzg

Add all greater values BST

http://www.geeksforgeeks.org/add-greater-values-every-node-given-bst/

Remove all nodes which don’t lie in any path with sum>= k

1) pass sum of root to its children
2) compare at each level wether we have got desired sum
  {
    i) if yes, return true from that node
    ii) else check if node is leaf node
      {
       a) if its a leaf node & sum is not desired one return false
     }
   pass sum upto this node to left subtree
   if left subtree return false
      remove left subtree node
   pass sum upto this node to right subtree
   if right subtree return false
      remove right subtree node
   if either of subtree has return tree
      return true
   else
     return false

Interview Questions

http://hissain.in/wordpress/?p=527

Connect Leaves Double Linked List

http://www.geeksforgeeks.org/connect-leaves-doubly-linked-list/

Deepest Leaf Node in Binary Tree

http://www.geeksforgeeks.org/deepest-left-leaf-node-in-a-binary-tree/

Closest Pari Points

http://stackoverflow.com/questions/9405660/closest-pair-of-points-algorithm

Reservoir Sampling

http://kebomix.wordpress.com/2011/01/09/reservoir-sampling-java/

http://larrylisblog.net/WebContents/Programming/ReservoirSampling.pdf

http://www.geeksforgeeks.org/reservoir-sampling/

Delete Last Node (Head not not given) LInked Lists

public void deleteLast(){
 //check if this is the last node
 if(this.next == null) {
  this = null;
  return;
 }
 
 //look 2 nodes ahead to see if we have reached the end
 Node temp = this;
 while(temp.next.next != null){
  temp = temp.next;
 }
 
 //Finally, move to last node and set it null
 temp = temp.next;
 temp = null;
}

Reverse Double Linked List

http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/

Unsorted LInked List Duplicates Removal

Sorting Algorithms

1. Insertion Sort
2. Merge Sort
3. Quick Sort
4. Heap Sort
5. Counting Sort
6. Radix Sort
7. Bucket Sort

     http://www.cs.carleton.edu/faculty/adalal/teaching/f04/117/notes/searchSort.pdf

     http://cusatstudymaterials.files.wordpress.com/2013/04/137877333-sorting-algorithms-in-java.pdf

     http://www.sorting-algorithms.com/

Merge Sort

Counting Number of Inversions Using Merge Sort

http://www.geeksforgeeks.org/counting-inversions/

Merge Sorted Linked Lists

Queue Reversal

Stack Reverse (O(n*2) time O(n) space)

Reverse Linked List

https://www.geeksforgeeks.org/delete-nth-node-from-the-end-of-the-given-linked-list/

http://edgblog.wordpress.com/2007/12/06/reversing-a-singly-linked-list-in-java/

public class ReverseList {
public static void main(String args[]) {
// build a singly linked list
// a -> b -> c -> d -> e
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
Node d = new Node("d");
Node e = new Node("e");
a.next = b;
b.next = c;
c.next = d;
d.next = e;
SinglyLinkedList list = new SinglyLinkedList();
list.head = a;
System.out.println("Original list");
list.print(list.head);
list.reverse();
System.out.println("\n\nList reversed with procedural method");
list.print(list.head);
list.reverse(null, list.head);
System.out.println("\n\nList re-reversed with recursive method");
list.print(list.head);
}
}

class SinglyLinkedList {
Node head;

public void print(Node node) {
System.out.print(node);
if (node.next != null) {
System.out.print(" -> ");
print(node.next);
}
}

// procedural reverse
public void reverse() {
Node n3 = head;
Node n2 = null;
Node n1 = null;
while (n3 != null) {
n1 = n2;
n2 = n3;
n3 = n2.next;
n2.next = n1;
}
head = n2;
}

// recursive reverse
public void reverse(Node n1, Node n2) {
Node n3 = n2.next;
n2.next = n1;
if (n3 != null) {
reverse(n2, n3);
} else {
head = n2;
}
}
}

class Node {
Node next;
String value;

Node(String value) {
this.value = value;
}

public String toString() {
return value;
}

}

Stack Using LinkedList

Height of BinaryTree

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

LCA BinaryTree

Vertical Sum in a Binary Tree

https://gist.github.com/dheeraj9823/7200759

In Pre Post Order Non Recursive BinaryTree

DeleteNode BST

public class BST {

public static void main(String [] args)
{
treeNode a = new treeNode();
a.setData(4);
treeNode b = new treeNode();
b.setData(2);
treeNode c = new treeNode();
c.setData(6);
treeNode d = new treeNode();
d.setData(1);
treeNode e = new treeNode();
e.setData(3);
treeNode f = new treeNode();
f.setData(5);
treeNode g = new treeNode();
g.setData(7);

a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
c.setLeft(f);
c.setRight(g);
BST bst = new BST();
treeNode node = bst.findbstNonrec(a, 7);
System.out.print(node.getData());
treeNode del = bst.deleteNodeBST(a, 3);

}

public treeNode findbst(treeNode root,int data)
{
if(root == null)
return null;
if(data < root.getData())
return findbst(root.getLeft(), data);
if(data > root.getData())
return findbst(root.getRight(),data);
return root;

}

public treeNode findbstNonrec(treeNode root, int data)
{
if(root == null)
return null;
while(root != null)
{
if(data < root.getData())
root = root.getLeft();
else if(data > root.getData())
root = root.getRight();
else
return root;
}
return null;
}

public treeNode deleteNodeBST(treeNode root , int data)
{
treeNode temp;
treeNode left,right;

if(root == null)
System.out.println("Element not in the tree");
else if(data < root.getData())
root.setLeft(deleteNodeBST(root.getLeft(),data)) ;
else if(data > root.getData())
root.setRight(deleteNodeBST(root.getRight(),data)) ;

else
{
if(root.getLeft() != null && root.getRight() !=null)
{
temp = FindMax(root.getLeft());
root.setData(temp.getData());
root.setLeft(deleteNodeBST(root.getLeft(), root.getData()));
}
else
{
temp = root;
if(root.getLeft() == null)
{
root = root.getRight();
}
else if(root.getRight() == null)
{
root = root.getLeft();
}

}
}

return root;
}

private treeNode FindMax(treeNode root) {
// TODO Auto-generated method stub

if(root == null)
return null;
else
if(root.getRight() == null)
return root;
else
return FindMax(root.getRight());

}

}

ZigZag Traversal BinaryTree

Diameter Binary Tree

Stack using Array

public class Stack {

public int tos;
public int []stk;

public Stack(int size)
{
tos = -1;
stk = new int[size];
}
public void push(int data)
{
if(tos==stk.length-1)
{
System.out.println("Stack is Full");
}
else
{
stk[++tos] = data;
System.out.println(stk[tos]);
}
}

public int pop()
{
if(tos==-1)
{
System.out.println("Stack is Empty");
return 0;
}
else
{
return stk[tos--];

}
}

public static void main(String []args)
{
Stack s = new Stack(4);
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.pop());
}
}

Reverse k nodes in a linkedlist

public class ReverseKNodes {

public static void main(String[] args) {

lnode a = new lnode();
a.setData(1);
lnode b = new lnode();
b.setData(2);
lnode c = new lnode();
c.setData(3);
lnode d = new lnode();
d.setData(4);
lnode e = new lnode();
e.setData(5);
lnode f = new lnode();
f.setData(6);
lnode g = new lnode();
g.setData(7);
lnode h = new lnode();
h.setData(8);
lnode i = new lnode();
i.setData(9);
lnode j = new lnode();
j.setData(10);
lnode k = new lnode();
k.setData(11);
a.setNext(b);
b.setNext(c);
c.setNext(d);
d.setNext(e);
e.setNext(f);
f.setNext(g);
g.setNext(h);
h.setNext(i);
i.setNext(j);
j.setNext(k);

ReverseKNodes r = new ReverseKNodes();
lnode finalhead = r.ReverseKnodes(3, a);
while(finalhead != null)
{
System.out.println(finalhead.getData());
finalhead = finalhead.getNext();
}

}

public lnode ReverseKnodes(int K, lnode head)
{
int count=0;
lnode cur= head , newHead,temp=null,next=null,poc=null,fpoc= null;
if(HasKNodes(cur, K-1))
{
newHead = GetPlusOneNode(K-1, cur);

}
else
newHead = head;
while(cur!=null && HasKNodes(cur, K))
{

fpoc = poc;
temp = GetPlusOneNode(K, cur);
poc = cur;

int i=0;
while(i{

next = cur.getNext();
cur.setNext(temp);
temp = cur;
cur = next;
i++;
}
if(count != 0)
fpoc.setNext(temp);
count++;

}

return newHead;
}

public boolean HasKNodes(lnode head, int K) {

lnode node;
int i;
for(i=0;head != null && i <= K -1;i++,head = head.getNext());

if(i==K)
{
return true;
}
else
return false;
}

public lnode GetPlusOneNode(int K,lnode head)
{
int i;
lnode kth;
for(i=0,kth=head;kth!= null&& i<= K-1;i++,kth = kth.getNext());
if(i==K && kth != null)
{
return kth;
}

return head.getNext();
}

}

class lnode {
private int data;
private lnode next;

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public lnode getNext() {
return next;
}

public void setNext(lnode next) {
this.next = next;
}
}