package dataStructure.tree;
public class SizeOfTree {
public static void main(String[] args) {
Node rL = new Node(null, 5, null);
Node rR = new Node(null, 15, null);
Node root = new Node(rL, 10, rR);
System.out.println(sizeOfTree(root));
}
public static int sizeOfTree(Node root){
if(null == root){
return 0;
}
return sizeOfTree(root.left) + 1 + sizeOfTree(root.right);
}
private static class Node{
@SuppressWarnings("unused")
public int key;
public Node left;
public Node right;
/**
* @param key
* @param left
* @param right
*/
public Node(Node left, int key, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
}
}
Thursday, June 8, 2017
Program to Calculate Size of a Binary tree
Number of nodes available in a tree will be called size of tree. Below is the recursive program to calculate size of a binary tree.
Monday, June 5, 2017
Breadth First Traversal Or Level Order Traversal
Breadth-first
search (BFS) is an algorithm for traversing or
searching tree or graph data
structures. It starts at the tree
root and explores the neighbor nodes
first, before moving to the next level neighbors.
Time complexity:
BFS require O(n) time as it
visits every node exactly once.
Extra Space:
Extra Space required for Level
Order Traversal is O(w) where w is maximum width of Binary Tree.
Java Code:
package dataStructure.tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @author Rajendar Kumar
*
*/
public class BFSWithQueue {
/**
* @param args
*/
public static void main(String[] args) {
Node rLl = new Node(null, 4, null);
Node rLr = new Node(null, 5, null);
Node rRl = new Node(null, 6, null);
Node rRr = new Node(null, 7, null);
Node rL = new Node(rLl, 2, rLr);
Node rR = new Node(rRl, 3, rRr);
Node root = new Node(rL, 1, rR);
List<Integer> list =bfs(root);
for (Integer integer : list) {
System.out.print(integer+" ");
}
}
public static List<Integer> bfs(Node root){
List<Integer> list = new ArrayList<>();
Queue<Node> hList = new LinkedList<>();
Node temp = root;
while(null != temp){
list.add(temp.key);
if(null != temp.left){
hList.add(temp.left);
}
if(null != temp.right){
hList.add(temp.right);
}
temp = hList.poll();
}
return list;
}
}
package dataStructure.tree;
/**
* @author Rajendar Kumar
*
*/
public class Node {
public int key;
public Node left;
public Node right;
public Node(Node left, int key, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
}
Wednesday, August 31, 2016
Find if an expression has duplicate parenthesis
Problem statement :
Given an balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if same sub-expression is surrounded by multiple parenthesis.
Examples:
Below expressions have duplicate parenthesis - ((a+b)+((c+d))) The subexpression "c+d" is surrounded by two pairs of brackets. (((a+(b)))+(c+d)) The subexpression "a+(b)" is surrounded by two pairs of brackets. (((a+(b))+c+d)) The whole expression is surrounded by two pairs of brackets. Below expressions don't have any duplicate parenthesis - ((a+b)+(c+d)) No subsexpression is surrounded by duplicate brackets. ((a+(b))+(c+d)) No subsexpression is surrounded by duplicate brackets.
It may be assumed that the given expression is valid and there are not any white spaces present. courtesy by geeksforgeeks .
Solution for this problem using stack data structure is below:
Trace string expression left to right and insert all characters till you receive right parenthesis. If you find right parenthesis, pop all the elements till first occurrence of left parenthesis including left parenthesis itself.
if top char itself is left parenthesis then duplicate parenthesis else no.
package com.raj.stack;
import java.util.Stack;
public class DuplicateParenthesis {
private final static Character RIGHT_PARENTHESIS=')';
private final static Character LEFT_PARENTHESIS='(';
/**
* @param args
*/
public static void main(String[] args) {
String exp1 = "((a+b)+((c+d)))";
String exp2 = "(((a+(b)))+(c+d))";
String exp3 = "(((a+(b))+c+d))";
String exp4 = "((a+b)+(c+d))";
String exp5 = "(a+((b))+(c+d))";
System.out.println("exp 1 : "+isDuplicateParenthesisFound(exp1));
System.out.println("exp 2 : "+isDuplicateParenthesisFound(exp2));
System.out.println("exp 3 : "+isDuplicateParenthesisFound(exp3));
System.out.println("exp 4 : "+isDuplicateParenthesisFound(exp4));
System.out.println("exp 5 : "+isDuplicateParenthesisFound(exp5));
}
private static boolean isDuplicateParenthesisFound(String exp){
Stack<Character> expstack = new Stack<>();
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) != RIGHT_PARENTHESIS){
push(expstack, exp.charAt(i));
}else if(pop(expstack, LEFT_PARENTHESIS)){
return true;
}
}
return false;
}
private static <T> void push(Stack<T> expstack, T t){
expstack.push(t);
}
private static <T> boolean pop(Stack<T> expstack, T condition){
if(expstack.pop()==condition){
return true;
}
while(expstack.pop() != condition);
return false;
}
}
Sunday, July 3, 2016
Design a stack that supports getMin() in O(1) time with extra space
Original problem statement from geeksforgeeks.org
This is the generic implementation of this stack data structure.
package com.raj.ds.stack;
import java.util.Comparator;
/**
* @author rajendar.bit@gmail.com
*
*/
public interface IStack <T>{
/**
* <p>This method will be used to push the element onto stack.<p>
*
* @param t
*/
public void push(T t);
/**
* <p>This method will be used to get and remove the top element from stack.<p>
* @return
*/
public T pop();
/**
* It will return the current size of the stack.<p>
* @return
*/
public int size();
/**
* @return
* <p> returns <code>true</code> if stack reached its capacity else <code>false</code>.<p>
*/
public boolean isFull();
/**
*
* @return
* returns <code>true</code> if stack empty else <code>false</code>.<p>
*/
public boolean isEmpty();
/**
* <p>It will return minimum element at current position of the stack.<p>
* @return
*
*/
public T minElement();
/**
*
* @return
* <p>It will return user defined {@link Comparator}<p>
*/
Comparator<? super T> comparator();
}
#################################################################################
package com.raj.ds.stack;
import java.util.Comparator;
/**
* @author rajendar.bit@gmail.com
*
*<p>Question: Design a Data Structure SpecialStack that supports all the stack operations<p>
*<p>like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should <p>
*<p>return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1).<p>
*<p> To implement SpecialStack, you should only use standard Stack data structure and no other data<p>
*
*
*/
public class MinStack<T> implements IStack<T>{
/**This Object array will be used to store elements for stack data structure **/
private Object stack[];
/**This Object array will be used to store minimum elements for stack data structure **/
private Object minStack[];
/** Capacity will be used to define the maximum size of stack**/
private int capacity;
/** Index will be used to store the element in Object array.**/
private int index;
/** DEFAULT_CAPACITY is the maximum default capacity of stack**/
private final static int DEFAULT_CAPACITY=10;
/**
* <p>{@linkplain Comparator} Will be used to compare the current minimum element with new element for user define class.<p>
* <p>User defined class must implement {@linkplain Comparator} interface.<p>
* **/
private final Comparator<? super T> comparator;
/**
* <p>This Constructor can be used for all wrapper classes with default {@link MinStack#capacity}<p>
*/
public MinStack() {
this.capacity = DEFAULT_CAPACITY;
this.comparator = null;
stack = new Object[this.capacity];
minStack= new Object[this.capacity];
}
/**
* <p>This Constructor can be used for all wrapper classes with user defined {@link MinStack#capacity}<p>
* @param capacity
*/
public MinStack( int capacity) {
this.capacity = capacity;
this.comparator = null;
stack = new Object[this.capacity];
minStack= new Object[this.capacity];
}
/**
*<p>This Constructor can be used for all user defined classes and comparator with default {@link MinStack#capacity}<p>
* @param comparator
*/
public MinStack(Comparator<? super T> comparator) {
this.capacity = DEFAULT_CAPACITY;
this.comparator = comparator;
stack = new Object[this.capacity];
minStack= new Object[this.capacity];
}
/**
* <p>This Constructor can be used for all user defined classes and comparator with user defined {@link MinStack#capacity}<p>
* @param comparator
* @param capacity
*/
public MinStack(Comparator<? super T> comparator, int capacity) {
this.capacity = capacity;
this.comparator = comparator;
stack = new Object[this.capacity];
minStack= new Object[this.capacity];
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#push(java.lang.Object)
*/
@SuppressWarnings("unchecked")
@Override
public void push(T t) {
if(this.isFull()){
throw new RuntimeException("Stack is over flow.");
}
if(this.isEmpty()){
minStack[index] = t;
}else if(null != comparator && 0<=comparator.compare((T)minStack[index-1],t)){
minStack[index]=t;
}else if(0<=((Comparable< ? super T>)minStack[index-1]).compareTo(t)){
minStack[index]=t;
}else{
minStack[index]=minStack[index-1];
}
stack[index++] = t;
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#pop()
*/
@Override
public T pop() {
@SuppressWarnings("unchecked")
T t = (T)stack[--index];
stack[index] = null;
minStack[index]= null;
return t;
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#size()
*/
@Override
public int size() {
return index;
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#isFull()
*/
@Override
public boolean isFull() {
return this.capacity==index;
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#isEmpty()
*/
@Override
public boolean isEmpty() {
return 0==index;
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#minElement()
*/
@SuppressWarnings("unchecked")
@Override
public T minElement() {
return (T)minStack[index-1];
}
/* (non-Javadoc)
* @see com.raj.ds.stack.IStack#comparator()
*/
@Override
public Comparator<? super T> comparator() {
return comparator;
}
}
#################################################################################
package com.raj.ds.stack;
/**
* @author rajendar.bit@gmail.com
*
*/
public class User {
public int id ;
public User(int id) {
this.id=id;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "id = "+id;
}
}
#################################################################################
package com.raj.ds.stack;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
MinStack<String> minStack = new MinStack<>(3);
minStack.push("A");
minStack.push("C");
minStack.push("B");
minStack.pop();
MinStack<User> userDefinedClassMinStack = new MinStack<>(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
return o1.id > o2.id ? 1: o1.id == o2.id ? 0 : -1;
}
});
User t = new User(1);
User t1 = new User(2);
User t3 = new User(3);
userDefinedClassMinStack.push(t);
userDefinedClassMinStack.push(t1);
userDefinedClassMinStack.push(t3);
userDefinedClassMinStack.pop();
}
}
Tuesday, June 21, 2016
Reverse stack using recursion in java
Here I am going to implement stack with fixed size of array and it also has behavior that will reverse the stack data.
package com.raj;
/**
* @author rajendar.bit@gmail.com
*
*/
public class Stack<T> {
private Object stack[];
private int capacity;
private int index;
private final static int DEFAULT_SIZE=10;
public Stack(){
this(DEFAULT_SIZE);
}
public Stack(int capacity){
this.capacity = capacity;
stack = new Object[capacity];
}
/**
*
* @return boolean
*/
public boolean isEmpty(){
return this.index==0;
}
/**
*
* @return boolean
*/
public boolean isFull(){
return this.capacity==this.index;
}
/**
* <p>This method will be used to push the data at top.<p>
* @param t
*/
public void push(T t){
if(isFull())
throw new IllegalArgumentException("Stack over flow.");
stack[index++]=t;
}
/**
* <p>This method will return and remove the top element.<p>
* @return
*/
@SuppressWarnings("unchecked")
public T pop(){
if(isEmpty())
throw new IllegalArgumentException("stack under flow.");
T t= (T)stack[--index];
stack[index] = null;
return t;
}
/**
* <p>This method will reverse the existing stack recursively.<p>
* @param size
*/
public void reverse(int size){
if(size==0){
return;
}
T t = pop();
reverse(size-1);
inserAtBottom(t);
}
/**
* <p>This method returns number of elements in stack.<p>
* @return
*/
public int size(){
return index;
}
/**
* <p>Inserts the element at bottom in existing stack.<p>
* @param t
*/
private void inserAtBottom(T t){
if(isEmpty()){
push(t);
}else{
T tmp = pop();
inserAtBottom(t);
push(tmp);
}
}
}
Main method:
package com.raj;
/**
* @author rajendar.bit@gmail.com
*
*/
public class StackMain{
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 10; i++) {
stack.push(i);
}
stack.reverse(stack.size());
while(stack.size()!=0){
System.out.println(stack.pop());
}
Stack<String> stacks = new Stack<>();
stacks.push("A");
stacks.push("B");
stacks.push("C");
stacks.reverse(stacks.size());
while(stacks.size()!=0){
System.out.println(stacks.pop());
}
}
}
Tuesday, August 11, 2015
Sieve of Eratosthenes Prime Number :-
Seive of Eratosthenes find the number on the based of upper bound, where you say, find the prime number less than equal to n.
Seive of Eratosthenes mark all the composite number first and then find all the non-composite number as prime number.
We know that 2 is the first prime number, so all the multiple of 2 would be composite number, Seive of Eratosthenes will mark all such number as composite and he will take next prime from the list and all it's multiple would be marked as composite number. This process will be followed till square root of n.
So Seive of Eratosthenes algorithm will be like below:-
- For all numbers m: 2 .. √n, if m is unmarked:
- add m to primes list;
- mark all it's multiples, starting from square, lesser or equal than n (k * m ≤ n, k ≥ m);
- otherwise, if m is marked, then it is a composite number;
- check all numbers in range √n .. n. All found unmarked numbers are primes, add them to list.
2 is prime number so we will mark all multiple of 2 starting from square of 2 means 4 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
9
|
10
|
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
21
|
22
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
|
31
|
32
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
|
41
|
42
|
43
|
44
|
45
|
46
|
47
|
48
|
49
|
50
|
|
51
|
52
|
53
|
54
|
55
|
56
|
57
|
58
|
59
|
60
|
|
61
|
62
|
63
|
64
|
65
|
66
|
67
|
68
|
69
|
70
|
|
71
|
72
|
73
|
74
|
75
|
76
|
77
|
78
|
79
|
80
|
|
81
|
82
|
83
|
84
|
85
|
86
|
87
|
88
|
89
|
90
|
|
91
|
92
|
93
|
94
|
95
|
96
|
97
|
98
|
99
|
100
|
3 is the next prime number so we will make all multiple of 3 starting from square of 3 means 9 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
9
|
10
|
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
21
|
22
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
|
31
|
32
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
|
41
|
42
|
43
|
44
|
45
|
46
|
47
|
48
|
49
|
50
|
|
51
|
52
|
53
|
54
|
55
|
56
|
57
|
58
|
59
|
60
|
|
61
|
62
|
63
|
64
|
65
|
66
|
67
|
68
|
69
|
70
|
|
71
|
72
|
73
|
74
|
75
|
76
|
77
|
78
|
79
|
80
|
|
81
|
82
|
83
|
84
|
85
|
86
|
87
|
88
|
89
|
90
|
|
91
|
92
|
93
|
94
|
95
|
96
|
97
|
98
|
99
|
100
|
5 is the next prime number so we will make all multiple of 5 starting from square of 5 means 25 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
9
|
10
|
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
21
|
22
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
|
31
|
32
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
|
41
|
42
|
43
|
44
|
45
|
46
|
47
|
48
|
49
|
50
|
|
51
|
52
|
53
|
54
|
55
|
56
|
57
|
58
|
59
|
60
|
|
61
|
62
|
63
|
64
|
65
|
66
|
67
|
68
|
69
|
70
|
|
71
|
72
|
73
|
74
|
75
|
76
|
77
|
78
|
79
|
80
|
|
81
|
82
|
83
|
84
|
85
|
86
|
87
|
88
|
89
|
90
|
|
91
|
92
|
93
|
94
|
95
|
96
|
97
|
98
|
99
|
100
|
By this way you can mark all the composite number and remaining non-marked number would be prime number as below table
|
|
2
|
3
|
|
5
|
|
7
|
|
|
|
|
11
|
|
13
|
|
|
|
17
|
|
19
|
|
|
|
|
23
|
|
|
|
|
|
29
|
|
|
31
|
|
|
|
|
|
37
|
|
|
|
|
41
|
|
43
|
|
|
|
47
|
|
|
|
|
|
|
53
|
|
|
|
|
|
59
|
|
|
61
|
|
|
|
|
|
67
|
|
|
|
|
71
|
|
73
|
|
|
|
|
|
79
|
|
|
|
|
83
|
|
|
|
|
|
89
|
|
|
|
|
|
|
|
|
97
|
|
|
|
Java implementation of Seive of Eratosthenes
package com.techguy.algo;
/**
* @author techguylearning@gmail.com
*
*/
public class PrimeNumberSieveOfEratosthenes {
public static void main(String[] args) {
new PrimeNumberSieveOfEratosthenes().primeNumbers(100);
}
public void primeNumbers(int upperBound){
boolean isComposite[] = new boolean[upperBound + 1];
int upperBoundSqrt = (int)Math.sqrt(upperBound);
for (int i = 2; i <=upperBoundSqrt ; i++) {
if(!isComposite[i]){
for(int k = i*i; k < upperBound; k = k+i){
isComposite[k]=true;
}
}
}
for (int i = 2; i < upperBound; i++) {
if(!isComposite[i]){
System.out.print(i+" ");
}
}
}
}
Note:- This algorithm is marking some number more than one times as composite that is drawback of this algorithm.
Subscribe to:
Posts (Atom)