Tuxer: May 2013

Thursday, May 2, 2013

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