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

	bool prunTree (tree *root, int sum, int K)
	{
	if (!root)
	return false;
	if (root->key + sum >= K)
	{
	return true;
	}
	if (!root->left && !root->right && ((root->key + sum) < K))
	{
	return false;
	}
	bool l_ret = prunTree (root->left, (root->key + sum), K);
	if (l_ret == false)
	{
	if (root->left)
	free (root->left);
	root->left = NULL;
	}
	bool r_ret = prunTree (root->right, (root->key + sum), K);
	if (r_ret == false)
	{
	if (root->right)
	free (root->right);
	root->right = NULL;
	}
	if (l_ret == true || r_ret == true)
	return true;
	else
	return false;
	}
	void pruning (tree **root, int K)
	{
	if (!*root)
	return;
	if ((*root)->key >= K)
	return;
	bool ret = prunTree (*root, 0, K);
	if (ret == false)
	{
	free (*root);
	*root = NULL;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	package intQuestions;
	import linkedList.Node;
	public class LinkedListDuplicatesRemoval {
	public static void main(String args[]){
	Node a = new Node();
	a.setData(1);
	Node b = new Node();
	b.setData(2);
	Node c = new Node();
	c.setData(1);
	Node d = new Node();
	d.setData(3);
	a.setNext(b);
	b.setNext(c);
	c.setNext(d);
	d.setNext(null);
	Node head = removeDuplicates(a);
	while(head != null) {
	System.out.println(head.getData()+"->");
	head = head.getNext();
	}
	}
	public static Node removeDuplicates(Node head){
	// iterate over the head and for each iteration..iterate again
	//over the complete list and comparing outer item with each inner item and
	//remove the item from list if it is same
	Node current = head;
	while(current != null) {
	Node prev = current;
	Node next = current.getNext();
	while(next != null){
	if(current.getData() == next.getData()){
	prev.setNext( next.getNext());
	} else {
	prev = next;
	}
	next = next.getNext();
	}
	current = current.getNext();
	}
	return head;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	package intQuestions;
	import java.util.ArrayList;
	import java.util.List;
	public class MergeSort_ {
	static List<Integer> originalList = new ArrayList<Integer>();
	static List<Integer> tempList = new ArrayList<Integer>();
	public static void main(String args[]){
	originalList.add(5);
	originalList.add(2);
	originalList.add(4);
	originalList.add(7);
	originalList.add(1);
	originalList.add(3);
	originalList.add(2);
	originalList.add(6);
	mergeSort( 0, originalList.size()-1);
	System.out.println(originalList.toString());
	}
	private static void mergeSort(int low,int high){
	if(low<high){
	int middle = (low+high)/2;
	mergeSort(low, middle);
	mergeSort(middle+1, high);
	merge(low,middle,high);
	}
	}
	private static void merge(int low,int middle,int high){
	tempList.clear();
	int i = low;
	int j = middle+1;
	while(i <= middle && j <= high){
	if(originalList.get(i) <= originalList.get(j)){
	tempList.add(originalList.get(i));
	i++;
	} else {
	tempList.add(originalList.get(j));
	j++;
	}
	}
	if(i <= middle){
	while(i<=middle) {
	tempList.add(originalList.get(i));
	i++;
	}
	}
	else if(j <= high){
	while(j<=high) {
	tempList.add(originalList.get(j));
	j++;
	}
	}
	for(int k=low;k<=high;k++){
	originalList.set(k, tempList.get(k-low));
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Counting Number of Inversions Using Merge Sort

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

Merge Sorted Linked Lists

	package intQuestions;
	import java.util.LinkedList;
	import java.util.List;
	import linkedList.Node;
	public class MergeLinkedLists {
	public static void main(String args[]) {
	Node n1 = new Node();
	n1.setData(1);
	Node n2 = new Node();
	n2.setData(3);
	Node n3 = new Node();
	n3.setData(5);
	n1.setNext(n2);
	n2.setNext(n3);
	n3.setNext(null);
	Node n4 = new Node();
	n4.setData(2);
	Node n5 = new Node();
	n5.setData(4);
	Node n6 = new Node();
	n6.setData(6);
	n4.setNext(n5);
	n5.setNext(n6);
	n6.setNext(null);
	Node result = mergeSortedLists(n1, n4);
	while(result != null) {
	if(result.getNext() == null) {
	System.out.print(result.getData());
	} else {
	System.out.print(result.getData() + "->");
	}
	result = result.getNext();
	}
	}
	public static Node mergeSortedLists(Node n1,Node n2) {
	Node result = null;
	if(n1 != null && n2 != null) {
	if(n1.getData() < n2.getData()) {
	result = n1;
	result.setNext(mergeSortedLists(n1.getNext(), n2));
	} else {
	result = n2;
	result.setNext(mergeSortedLists(n1, n2.getNext()));
	}
	} else if(n1 != null) {
	result = n1;
	} else if(n2 != null) {
	result = n2;
	}
	return result;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Queue Reversal

	package linkedList;
	import java.util.Stack;
	public class QueueReversal {
	public static void main(String args[]) throws Exception{
	Queue queue = new Queue();
	Node a = new Node();
	a.setData(1);
	Node b = new Node();
	b.setData(2);
	Node c = new Node();
	c.setData(3);
	Node d = new Node();
	d.setData(4);
	Node e = new Node();
	e.setData(5);
	e.setNext(null);
	queue.enQueue(a);
	queue.enQueue(b);
	queue.enQueue(c);
	queue.enQueue(d);
	queue.enQueue(e);
	queue.display();
	Queue reverseQueue = reverse(queue);
	System.out.println("reversed queue");
	reverseQueue.display();
	}
	public static Queue reverse(Queue queue) throws Exception{
	Stack<Node> stack = new Stack<Node>();
	while(!queue.isEmpty()){
	stack.push(queue.deQueue());
	}
	while(!stack.isEmpty()) {
	queue.enQueue(stack.pop());
	}
	return queue;
	}
	}
	package linkedList;
	public class Queue {
	private Node front;
	private Node rear;
	public Node getFront() {
	return front;
	}
	public void setFront(Node front) {
	this.front = front;
	}
	public Node getRear() {
	return rear;
	}
	public void setRear(Node rear) {
	this.rear = rear;
	}
	public boolean isEmpty() {
	return front == null ;
	}
	public void enQueue(Node newNode) {
	if(isEmpty()) {
	front = newNode;
	rear = front;
	} else {
	Node temp = rear;
	temp.setNext(newNode);
	rear = newNode;
	rear.setNext(null);
	}
	}
	public Node deQueue() throws Exception{
	Node temp;
	if(isEmpty()) {
	throw new Exception("Queue EMPTY");
	} else {
	temp = front;
	front = front.getNext();
	}
	return temp;
	}
	public void display() {
	Node temp = front;
	while(temp != null){
	System.out.print(temp.getData());
	temp = temp.getNext();
	if(temp != null)
	System.out.print("->");
	}
	System.out.println();
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	package linkedList;
	import java.util.Stack;
	public class StackReversal {
	public static void main(String args[]) {
	Stack<Integer> stack = new Stack<Integer>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	System.out.println(stack.toString());
	reverseStack(stack);
	System.out.println(stack.toString());
	}
	private static void reverseStack(Stack<Integer> stack) {
	if(stack.isEmpty()) {
	return;
	}
	int temp =stack.pop();
	reverseStack(stack);
	insertAtBottom(stack,temp);
	}
	private static void insertAtBottom(Stack<Integer> stack, int data) {
	if(stack.isEmpty()) {
	stack.push(data);
	return;
	}
	int temp = stack.pop();
	insertAtBottom(stack, data);
	stack.push(temp);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	import java.io.*;
	class Node {
	public int item;
	public Node next;
	public Node(int val) {
	item = val;
	}
	public void displayNode() {
	System.out.println("[" + item + "] ");
	}
	}
	class LinkedList {
	private Node first;
	public LinkedList() {
	first = null;
	}
	public boolean isEmpty() {
	return (first == null);
	}
	public void insert(int val)// inserts at beginning of list
	{
	Node newNode = new Node(val);
	newNode.next = first;
	first = newNode;
	}
	public Node delete()// deletes at beginning of list
	{
	Node temp = first;
	first = first.next;
	return temp;
	}
	public void display() {
	System.out.println("Elements from top to bottom");
	Node current = first;
	while (current != null) {
	current.displayNode();
	current = current.next;
	}
	System.out.println("");
	}
	}
	class Stack {
	private LinkedList listObj;
	public Stack() {
	listObj = new LinkedList();
	}
	public void push(int num) {
	listObj.insert(num);
	}
	public Node pop() {
	return listObj.delete();
	}
	public boolean isEmpty() {
	return listObj.isEmpty();
	}
	public void displayStack() {
	System.out.print("Stack : ");
	listObj.display();
	}
	}
	class StackLinkedListBlog {
	public static void main(String[] args) throws IOException {
	Stack demo = new Stack();
	demo.push(10);
	demo.push(20);
	demo.displayStack();
	demo.push(30);
	demo.push(40);
	demo.displayStack();
	demo.pop();
	demo.pop();
	System.out.println("Two elements are popped");
	demo.displayStack();
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	public class LCA {
	public static void main(String [] args)
	{
	treeNode a = new treeNode();
	a.setData(1);
	treeNode b = new treeNode();
	b.setData(2);
	treeNode c = new treeNode();
	c.setData(3);
	treeNode d = new treeNode();
	d.setData(4);
	treeNode e = new treeNode();
	e.setData(5);
	treeNode f = new treeNode();
	f.setData(6);
	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);
	LCA lca = new LCA();
	treeNode ans = lca.lca(a, d, e);
	}
	public treeNode lca(treeNode root , treeNode a ,treeNode b)
	{
	treeNode l,r;
	if(root == null)
	{
	return root;
	}
	if(root == a || root == b)
	{
	return root;
	}
	l = lca(root.getLeft(), a, b);
	r = lca(root.getRight(), a, b);
	if(l != null)
	{
	if(r!= null)
	return root;
	}
	return l != null?l:r;
	}
	}
	class treeNode {
	private int data;
	private treeNode left;
	private treeNode right;
	public int getData() {
	return data;
	}
	public void setData(int data) {
	this.data = data;
	}
	public treeNode getLeft() {
	return left;
	}
	public void setLeft(treeNode left) {
	this.left = left;
	}
	public treeNode getRight() {
	return right;
	}
	public void setRight(treeNode right) {
	this.right = right;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Vertical Sum in a Binary Tree

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

	import java.util.HashMap;
	public class VerticalSum {
	public static void main(String[] args) {
	treeNode a = new treeNode();
	a.setData(1);
	treeNode b = new treeNode();
	b.setData(2);
	treeNode c = new treeNode();
	c.setData(3);
	treeNode d = new treeNode();
	d.setData(4);
	treeNode e = new treeNode();
	e.setData(5);
	treeNode f = new treeNode();
	f.setData(6);
	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);
	Tree t = new Tree(a);
	t.VerticalSum();
	}
	}
	class Tree {
	private treeNode root;
	public Tree() {
	root = null;
	}
	public Tree(treeNode n) {
	root = n;
	}
	public void VerticalSum() {
	VerticalSum(root);
	}
	private void VerticalSum(treeNode root) {
	if (root == null) {
	return;
	}
	HashMap hm = new HashMap();
	VerticalSumUtil(root, 0, hm);
	if (hm != null)
	System.out.println(hm.entrySet());
	}
	private void VerticalSumUtil(treeNode root, int hd, HashMap hm) {
	if (root == null)
	return;
	VerticalSumUtil(root.getLeft(), hd - 1, hm);
	int prevSum = hm.get(hd) == null ? 0 : hm.get(hd);
	hm.put(hd, prevSum + root.getData());
	VerticalSumUtil(root.getRight(), hd + 1, hm);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

In Pre Post Order Non Recursive BinaryTree

	import java.util.HashMap;
	public class VerticalSum {
	public static void main(String[] args) {
	treeNode a = new treeNode();
	a.setData(1);
	treeNode b = new treeNode();
	b.setData(2);
	treeNode c = new treeNode();
	c.setData(3);
	treeNode d = new treeNode();
	d.setData(4);
	treeNode e = new treeNode();
	e.setData(5);
	treeNode f = new treeNode();
	f.setData(6);
	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);
	Tree t = new Tree(a);
	t.VerticalSum();
	}
	}
	class Tree {
	private treeNode root;
	public Tree() {
	root = null;
	}
	public Tree(treeNode n) {
	root = n;
	}
	public void VerticalSum() {
	VerticalSum(root);
	}
	private void VerticalSum(treeNode root) {
	if (root == null) {
	return;
	}
	HashMap hm = new HashMap();
	VerticalSumUtil(root, 0, hm);
	if (hm != null)
	System.out.println(hm.entrySet());
	}
	private void VerticalSumUtil(treeNode root, int hd, HashMap hm) {
	if (root == null)
	return;
	VerticalSumUtil(root.getLeft(), hd - 1, hm);
	int prevSum = hm.get(hd) == null ? 0 : hm.get(hd);
	hm.put(hd, prevSum + root.getData());
	VerticalSumUtil(root.getRight(), hd + 1, hm);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

	import java.util.Stack;
	public class PreInPost {
	public static void main(String [] args)
	{
	treeNode a = new treeNode();
	a.setData(1);
	treeNode b = new treeNode();
	b.setData(2);
	treeNode c = new treeNode();
	c.setData(3);
	treeNode d = new treeNode();
	d.setData(4);
	treeNode e = new treeNode();
	e.setData(5);
	treeNode f = new treeNode();
	f.setData(6);
	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);
	PreInPost p = new PreInPost();
	p.PreOrder(a);
	System.out.println();
	p.InOrder(a);
	p.PostOrder(a);
	}
	public void PreOrder(treeNode root)
	{
	if(root == null)
	{
	return;
	}
	Stack s = new Stack();
	while(true)
	{
	while(root!=null)
	{
	System.out.print(root.getData());
	System.out.print(" ");
	s.push(root);
	root = root.getLeft();
	}
	if(s.isEmpty())
	break;
	root = (treeNode)s.pop();
	root = root.getRight();
	}
	}
	public void InOrder(treeNode root)
	{
	if(root == null)
	{
	return;
	}
	Stack s = new Stack();
	while(true)
	{
	while(root!=null)
	{
	s.push(root);
	root = root.getLeft();
	}
	if(s.isEmpty())
	break;
	root = (treeNode)s.pop();
	System.out.print(root.getData());
	System.out.print(" ");
	root = root.getRight();
	}
	}
	public void PostOrder(treeNode root)
	{
	int count =0;
	treeNode Root = root;
	if(root == null)
	{
	return;
	}
	Stack s = new Stack();
	while(true)
	{
	if(root!=null)
	{
	s.push(root);
	root = root.getLeft();
	}
	else
	{
	if(s.isEmpty())
	return;
	else
	{
	if(((treeNode)s.peek()).getRight() == null)
	{
	root = (treeNode) s.pop();
	System.out.print(root.getData());
	System.out.print(" ");
	if(root == ((treeNode)s.peek()).getRight())
	{
	System.out.print(((treeNode)s.peek()).getData());
	System.out.print(" ");
	s.pop();
	}
	}
	}
	if(!s.isEmpty())
	{
	if((treeNode)s.peek() == Root)
	{
	count++;
	if(count > 1)
	{
	System.out.print(Root.getData());
	return;
	}
	}
	root = ((treeNode)s.peek()).getRight();
	}
	else
	root = null;
	}
	}
	}
	public void postorder(treeNode root ) {
	if( root == null ) return;
	Stack stack = new Stack( );
	treeNode current = root;
	while( true ) {
	if( current != null ) {
	if( current.getRight() != null ) stack.push( current.getRight() );
	stack.push( current );
	current = current.getLeft();
	continue;
	}
	if( stack.isEmpty( ) ) return;
	current = stack.pop( );
	if( current.getRight() != null && ! stack.isEmpty( ) && current.getRight() == stack.peek( ) ) {
	stack.pop( );
	stack.push( current );
	current = current.getRight();
	} else {
	System.out.print( current.getData() + " " );
	current = null;
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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

	import java.util.Stack;
	public class ZigZag {
	public static void main(String [] args)
	{
	treeNode a = new treeNode();
	a.setData(1);
	treeNode b = new treeNode();
	b.setData(2);
	treeNode c = new treeNode();
	c.setData(3);
	treeNode d = new treeNode();
	d.setData(4);
	treeNode e = new treeNode();
	e.setData(5);
	treeNode f = new treeNode();
	f.setData(6);
	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);
	ZigZag z = new ZigZag();
	z.ZigZagTraversal(a);
	}
	public void ZigZagTraversal(treeNode root)
	{
	treeNode temp;
	int lefttoright =1;
	if(root==null) return;
	Stack c = new Stack();
	Stack n = new Stack();
	c.push(root);
	while(!c.isEmpty())
	{
	temp = c.pop();
	if(temp != null)
	{
	System.out.print(temp.getData());
	System.out.print(" ");
	if(lefttoright >0) {
	if(temp.getLeft()!= null)
	n.push(temp.getLeft());
	if(temp.getRight() != null)
	n.push(temp.getRight());
	}
	else
	{
	if(temp.getRight() != null)
	n.push(temp.getRight());
	if(temp.getLeft()!= null)
	n.push(temp.getLeft());
	}
	}
	if(c.isEmpty())
	{
	lefttoright = 1 - lefttoright;
	Stack tmp = new Stack();
	tmp = n;
	n = c;
	c = tmp;
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Diameter Binary Tree

	public class Diameter {
	public static void main(String args[]) {
	BinaryTreeNode node1 = new BinaryTreeNode();
	BinaryTreeNode node2 = new BinaryTreeNode();
	BinaryTreeNode node3 = new BinaryTreeNode();
	node1.setData(1);
	node1.setLeft(node2);
	node1.setRight(node3);
	node2.setData(2);
	node2.setLeft(null);
	node2.setRight(null);
	node3.setData(3);
	node3.setLeft(null);
	node3.setRight(null);
	int diameter = diameterOfBinaryTree(node1);
	System.out.println(diameter);
	}
	public static int diameterOfBinaryTree(BinaryTreeNode node) {
	if (node == null) {
	return 0;
	}
	int leftHeight = heightOfBinaryTree(node.getLeft());
	int rightHeight = heightOfBinaryTree(node.getRight());
	int leftDiameter = diameterOfBinaryTree(node.getLeft());
	int rightDiameter = diameterOfBinaryTree(node.getRight());
	return Math.max(leftHeight + rightHeight + 1,
	Math.max(leftDiameter, rightDiameter));
	}
	public static int heightOfBinaryTree(BinaryTreeNode node) {
	if (node == null) {
	return 0;
	} else {
	return 1 + Math.max(heightOfBinaryTree(node.getLeft()),
	heightOfBinaryTree(node.getRight()));
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

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;
}
}