Creating mirror of BST

	package bst;
	/**
	* Created by panded4
	*/
	public class CreateBSTMirror {
	public static void main(String[] args) {
	TNode n1 = new TNode(5);
	n1.left = new TNode(10);
	n1.right = new TNode(15);
	n1.left.left = new TNode(20);
	n1.left.right = new TNode(25);
	n1.right.left = new TNode(30);
	n1.right.right = new TNode(35);
	inOrder(n1);
	createMirror(n1);
	System.out.println("\n");
	inOrder(n1);
	}
	private static void inOrder(TNode n1) {
	if (n1 == null)
	return;
	inOrder(n1.left);
	System.out.print(n1.data + " ");
	inOrder(n1.right);
	}
	static TNode createMirror(TNode root) {
	if (root == null)
	return root;
	TNode left = createMirror(root.left);
	TNode right = createMirror(root.right);
	root.left = right;
	root.right = left;
	return root;
	}
	}
	class TNode {
	int data;
	TNode left, right;
	public TNode(int data) {
	left = right = null;
	this.data = data;
	}
	}

view raw CreateBSTMirror.java hosted with ❤ by GitHub

QuickSort using java

	/**
	* Created by panded4
	* reference: Introduction to Algorithms by Cormen logic
	*/
	public class QuickSortAgain {
	static int partition(int arr[], int p, int r) {
	int x = arr[r];
	int i = p - 1;
	for (int j = p; j < r - 1; j++) {
	if (arr[j] >= x) {
	i += 1;
	swap(arr[i], arr[j]);
	}
	}
	swap(arr[i + 1], arr[r]);
	return i + 1;
	}
	static void swap(int m, int n) {
	int temp = 0;
	temp = m;
	m = n;
	m = temp;
	}
	static void quick(int arr[], int p, int r) {
	if (p < r) {
	int q = partition(arr, p, r);
	quick(arr, p, q - 1);
	quick(arr, q + 1, r);
	}
	}
	public static void main(String[] args) {
	int data[] = {10, 20, 30, 40, 50, 60, 71, 80, 90, 91};
	quick(data, 0, data.length - 1);
	for (int i : data) {
	System.out.print(i);
	System.out.print(" ");
	}
	}
	}

view raw QuickSortAgain.java hosted with ❤ by GitHub

Height of BST

	package bst;
	import static java.lang.Math.max;
	/**
	* Created by panded4
	*/
	public class HeightBST {
	int leftH = 0, rightH = 0;
	private TreeNode head;
	public HeightBST() {
	this.head = createTree();
	}
	public static void main(String[] args) {
	HeightBST heightBST = new HeightBST();
	System.out.println(heightBST.calculateHeight(heightBST.head));
	}
	private TreeNode createTree() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	TreeNode n7 = new TreeNode(7);
	TreeNode n8 = new TreeNode(8);
	TreeNode n9 = new TreeNode(9);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n2.right = n5;
	n3.left = n6;
	n3.right = n7;
	n4.left = n8;
	n4.right = n9;
	return n1;
	}
	int calculateHeight(TreeNode head) {
	if (head == null) {
	return 0;
	}
	leftH = calculateHeight(head.left);
	rightH = calculateHeight(head.right);
	return 1 + max(leftH, rightH);
	}
	}

view raw HeightBST.java hosted with ❤ by GitHub

Level Order Traversal and printing in zigzag pattern java

	package bst;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Queue;
	import java.util.Stack;
	public class Graph_Traverse {
	private static final TreeNode EMPTY = new TreeNode(-1);
	private TreeNode head;
	public Graph_Traverse() {
	this.head = createTree();
	}
	public static void main(String[] args) {
	Graph_Traverse graph_Traverse = new Graph_Traverse();
	graph_Traverse.PrintLevelOrder();
	}
	private TreeNode createTree() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	TreeNode n7 = new TreeNode(7);
	TreeNode n8 = new TreeNode(8);
	TreeNode n9 = new TreeNode(9);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n2.right = n5;
	n3.left = n6;
	n3.right = n7;
	n4.left = n8;
	n4.right = n9;
	return n1;
	}
	public void PrintLevelOrder() {
	boolean forward = true;
	Queue<TreeNode> q = new LinkedList<TreeNode>();
	Stack<TreeNode> s = new Stack<TreeNode>();
	q.add(this.head);
	q.add(EMPTY);
	while (!q.isEmpty()) {
	TreeNode g = q.remove();
	if (g.left != null) {
	q.add(g.left);
	}
	if (g.right != null) {
	q.add(g.right);
	}
	if (g.equals(EMPTY)) {
	if (!q.isEmpty()) {
	q.add(EMPTY);
	}
	forward = !forward;
	while (!s.isEmpty()) {
	System.out.print(s.pop().data + " ");
	}
	continue;
	}
	if (forward == true) {
	System.out.print(g.data + " ");
	} else {
	s.push(g);
	}
	}
	}
	}
	class TreeNode {
	int data;
	TreeNode left, right;
	TreeNode(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	@Override
	public boolean equals(Object n) {
	return (this.data == ((TreeNode) n).data);
	}
	}

view raw Graph_Traverse.java hosted with ❤ by GitHub

	package bst;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Created by panded4
	*/
	public class LevelOrderTraversalBST {
	public static void main(String[] args) throws java.lang.Exception {
	Node root = new Node(5);
	root.left = new Node(10);
	root.right = new Node(15);
	root.left.left = new Node(20);
	root.left.right = new Node(25);
	root.right.left = new Node(30);
	root.right.right = new Node(35);
	LevelOrderTraversalBST l = new LevelOrderTraversalBST();
	System.out.println("Breadth First Search : ");
	l.levelOrderQueue(root);
	}
	public void levelOrderQueue(Node root) {
	Queue<Node> q = new LinkedList<Node>();
	if (root == null)
	return;
	q.add(root);
	int count = 1;
	while (!q.isEmpty()) {
	Node n = (Node) q.remove();
	System.out.print(" " + n.data);
	count += 1;
	if (n.left != null)
	q.add(n.left);
	if (n.right != null)
	q.add(n.right);
	}
	}
	}
	class Node {
	int data;
	Node left;
	Node right;
	public Node(int data) {
	this.data = data;
	this.left = null;
	this.right = null;
	}
	}

view raw LevelOrderTraversalBST.java hosted with ❤ by GitHub

Palindrome DP

	import java.util.HashSet;
	import java.util.Set;
	/**
	* Created by panded4
	*/
	public class Palindrome2 {
	public static Set<String> palindromes(final String input) {
	final Set<String> result = new HashSet<>();
	for (int i = 0; i < input.length(); i++) {
	// expanding even length palindromes:
	expandPalindromes(result, input, i, i + 1);
	// expanding odd length palindromes:
	expandPalindromes(result, input, i, i);
	}
	return result;
	}
	public static void expandPalindromes(final Set<String> result, final String s, int i, int j) {
	while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
	result.add(s.substring(i, j + 1));
	i--;
	j++;
	}
	}
	public static void main(String[] args) {
	for (String set : palindromes("liiri")) {
	System.out.println(set);
	}
	}
	}

view raw Palindrome2.java hosted with ❤ by GitHub

BFS in Graph

	package graph;
	import java.util.Iterator;
	import java.util.LinkedList;
	/**
	* Created by panded4 on 6/11/2017.
	*/
	public class BFS {
	int v;
	LinkedList<Integer> adj[];
	public BFS(int v) {
	this.v = v;
	adj = new LinkedList[v];
	for (int i = 0; i < v; i++) {
	adj[i] = new LinkedList<>();
	}
	}
	public static void main(String[] args) {
	BFS g = new BFS(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);
	System.out.println("Following is Breadth First Traversal " +
	"(starting from vertex 2)");
	g.bfsUtil(2);
	}
	private void bfsUtil(int s) {
	boolean visited[] = new boolean[v];
	LinkedList<Integer> queue = new LinkedList<Integer>();
	visited[s]=true;
	queue.add(s);
	while (queue.size() != 0)
	{
	s = queue.poll();
	System.out.print(s+" ");
	Iterator<Integer> i = adj[s].listIterator();
	while (i.hasNext())
	{
	int n = i.next();
	if (!visited[n])
	{
	visited[n] = true;
	queue.add(n);
	}
	}
	}
	}
	private void addEdge(int i, int w) {
	adj[i].add(w);
	}
	}

view raw BFS.java hosted with ❤ by GitHub

DFS in Graph

	package graph;
	import java.util.Iterator;
	import java.util.LinkedList;
	/**
	* Created by panded4
	*/
	public class DFS {
	LinkedList<Integer> adj[];
	private int v;
	public DFS(int v) {
	this.v = v;
	adj = new LinkedList[v];
	for (int i = 0; i < v; i++) {
	adj[i] = new LinkedList<>();
	}
	}
	public static void main(String[] args) {
	DFS g = new DFS(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);
	System.out.println("Following is Depth First Traversal " +
	"(starting from vertex 2)");
	g.callDFS(2);
	}
	private void callDFS(int i) {
	boolean[] visited = new boolean[v];
	dfsUtil(i, visited);
	}
	private void dfsUtil(int i, boolean[] visited) {
	visited[i] = true;
	System.out.print(i + " ");
	Iterator<Integer> iterator = adj[i].listIterator();
	while (iterator.hasNext()) {
	int n = iterator.next();
	if (!visited[n])
	dfsUtil(n, visited);
	}
	}
	private void addEdge(int i, int w) {
	adj[i].add(w);
	}
	}

view raw DFS.java hosted with ❤ by GitHub

LCS using DP

	package lcs;
	/**
	* Created by panded4
	*/
	public class LCSTest {
	public static void main(String[] args) {
	LCSTest lcs = new LCSTest();
	String s1 = "DEEP";
	String s2 = "JDEEKPA";
	char[] X = s1.toCharArray();
	char[] Y = s2.toCharArray();
	int m = X.length;
	int n = Y.length;
	lcs.lcs(X, Y, m, n);
	}
	void lcs(char[] X, char[] Y, int m, int n) {
	int L[][] = new int[m + 1][n + 1];
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0 || j == 0)
	L[i][j] = 0;
	else if (X[i - 1] == Y[j - 1])
	L[i][j] = L[i - 1][j - 1] + 1;
	else
	L[i][j] = max(L[i - 1][j], L[i][j - 1]);
	}
	}
	int index = L[m][n];
	int[] lcs = new int[index + 1];
	int i = m, j = n;
	while (i > 0 && j > 0) {
	if (X[i - 1] == Y[j - 1]) {
	lcs[index - 1] = X[i - 1];
	i--;
	j--;
	index--;
	} else if (L[i - 1][j] > L[i][j - 1])
	i--;
	else
	j--;
	}
	for (int lc : lcs
	) {
	System.out.println((char) lc);
	}
	}
	int max(int a, int b) {
	return (a > b) ? a : b;
	}
	}

view raw LCSTest.java hosted with ❤ by GitHub