Category Archives: Algorithm

It works on negative cycle.

Implemented Code:

Time Complexity:

O([E].[V])

Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html

Leave a comment

Posted in Algo Unsolved, Bellman Ford, Single Source Shortest Path

Tagged not greedy

Dijkstra

Posted on July 10, 2017 | Leave a comment

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cost[10][10],path[10][10],i,j,n,p,v,min,index=1;
    int distance[10],row,column;

    cout<<"Enter no. of nodes: ";
    cin>>n;
    cout<<"Enter cost matrix: \n";
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>cost[i][j];
        }
    }
    printf("Enter the node you want to visit:");
    cin>>v;
    printf("Enter the path for the selected node:");
    cin>>p;
    cout<<"Enter the path matrix: \n";
    for(i=1;i<=p;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>path[i][j];
        }
    }

    for(i=1;i<=p;i++){
        distance[i]=0;
        row=1;
        for(j=1;j<=n;j++)
        {
            if(row!=v)
            {
                column=path[i][j+1];
                distance[i]=distance[i]+cost[row][column];

            }
            row=column;

        }

    }
    min=distance[1];
for(i=1;i<=p;i++)
{
    if(distance[i]<=min)
    {
        min=distance[i];
        index=i;
    }
}
cout<<"The minimum distance is:";
cout<<min;
for(i=1;i<=n;i++){
    if(path[index][i]!=0)
    {
        printf("-->%d",path[index][i]);
    }
}

}

#include<bits/stdc++.h>

using namespace std;

int main(){

int cost[10][10],path[10][10],i,j,n,p,v,min,index=1;

int distance[10],row,column;

cout<<"Enter no. of nodes: ";

cin>>n;

cout<<"Enter cost matrix: \n";

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

cin>>cost[i][j];

}

printf("Enter the node you want to visit:");

cin>>v;

printf("Enter the path for the selected node:");

cin>>p;

cout<<"Enter the path matrix: \n";

for(i=1;i<=p;i++)

{

for(j=1;j<=n;j++)

{

cin>>path[i][j];

}

for(i=1;i<=p;i++){

distance[i]=0;

row=1;

for(j=1;j<=n;j++)

{

if(row!=v)

{

column=path[i][j+1];

distance[i]=distance[i]+cost[row][column];

}

row=column;

}

min=distance[1];

for(i=1;i<=p;i++)

{

if(distance[i]<=min)

{

min=distance[i];

index=i;

}

cout<<"The minimum distance is:";

cout<<min;

for(i=1;i<=n;i++){

if(path[index][i]!=0)

{

printf("-->%d",path[index][i]);

}

output:

Enter no. of nodes: 5
Enter cost matrix:
0
4
0
8
0
4
0
3
0
0
0
3
0
4
0
8
0
4
0
7
0
0
0
7
0
Enter the node you want to visit:5
Enter the path for the selected node:2
Enter the path matrix: 1
2
3
4
5
1
4
5
0
0
The minimum distance is:15-->1-->4-->5

Enter no. of nodes: 5

Enter cost matrix:

Enter the node you want to visit:5

Enter the path for the selected node:2

Enter the path matrix: 1

The minimum distance is:15-->1-->4-->5

Complexity:
O(E+V^2)

We are using here adjacency matrix list

Leave a comment

Posted in Dijkstra, Graph, Single Source Shortest Path

Topological Sort

Posted on July 10, 2017 | Leave a comment

code:

// A Java program to print topological sorting of a DAG
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency List

    //Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    // Function to add an edge into the graph
    void addEdge(int v,int w) { adj[v].add(w); }

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    // The function to do Topological Sort. It uses
    // recursive topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }

    // Driver method
    public static void main(String args[])
    {
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Following is a Topological " +
                "sort of the given graph");
        g.topologicalSort();
    }
}

// A Java program to print topological sorting of a DAG

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency

// list representation

class Graph

{

private int V; // No. of vertices

private LinkedList<Integer> adj[]; // Adjacency List

//Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i<v; ++i)

adj[i] = new LinkedList();

}

// Function to add an edge into the graph

void addEdge(int v,int w) { adj[v].add(w); }

// A recursive function used by topologicalSort

void topologicalSortUtil(int v, boolean visited[],

Stack stack)

{

// Mark the current node as visited.

visited[v] = true;

Integer i;

// Recur for all the vertices adjacent to this

// vertex

Iterator<Integer> it = adj[v].iterator();

while (it.hasNext())

{

i = it.next();

if (!visited[i])

topologicalSortUtil(i, visited, stack);

}

// Push current vertex to stack which stores result

stack.push(new Integer(v));

}

// The function to do Topological Sort. It uses

// recursive topologicalSortUtil()

void topologicalSort()

{

Stack stack = new Stack();

// Mark all the vertices as not visited

boolean visited[] = new boolean[V];

for (int i = 0; i < V; i++)

visited[i] = false;

// Call the recursive helper function to store

// Topological Sort starting from all vertices

// one by one

for (int i = 0; i < V; i++)

if (visited[i] == false)

topologicalSortUtil(i, visited, stack);

// Print contents of stack

while (stack.empty()==false)

System.out.print(stack.pop() + " ");

}

// Driver method

public static void main(String args[])

{

// Create a graph given in the above diagram

Graph g = new Graph(6);

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1);

System.out.println("Following is a Topological " +

"sort of the given graph");

g.topologicalSort();

}

Output:

Following is a Topological sort of the given graph
5 4 2 3 1 0

1 2	Following is a Topological sort of the given graph 5 4 2 3 1 0

Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge

code courtesy:

Topological Sorting

I understood the theory but need to understand the code well later

Leave a comment

Posted in Graph, Topological Sort

Bucket Sort

Posted on July 7, 2017 | Leave a comment

Pseudocode:

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

bucketSort(arr[], n)

1) Create n empty buckets (Or lists).

2) Do following for every array element arr[i].

.......a) Insert arr[i] into bucket[n*array[i]]

3) Sort individual buckets using insertion sort.

4) Concatenate all sorted buckets.

Implemented Code:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(float A[],int n){
    //1. create an n empty buckets
    vector<float> b[n];
    //2. Put array elements in different buckets
    for(int i=0;i<n;i++)
    {
        int bi=n*A[i]; //index in bucket
        b[bi].push_back(A[i]);
    }
    //3. Sort individual buckets
    for(int i=0;i<n;i++)
    {
        sort(b[i].begin(),b[i].end());
    }
    //4. concatenate all bucket into an array
    int index=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<b[i].size();j++)
        {
            A[index++]=b[i][j];
        }
    {

    }
}
int main()
{
    float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
    int n=sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr,n);
    cout<<"Sorted array is\n";
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

void bucketSort(float A[],int n){

//1. create an n empty buckets

vector<float> b[n];

//2. Put array elements in different buckets

for(int i=0;i<n;i++)

{

int bi=n*A[i]; //index in bucket

b[bi].push_back(A[i]);

}

//3. Sort individual buckets

for(int i=0;i<n;i++)

{

sort(b[i].begin(),b[i].end());

}

//4. concatenate all bucket into an array

int index=0;

for(int i=0;i<n;i++)

for(int j=0;j<b[i].size();j++)

{

A[index++]=b[i][j];

}

{

}

int main()

{

float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};

int n=sizeof(arr)/sizeof(arr[0]);

bucketSort(arr,n);

cout<<"Sorted array is\n";

for(int i=0;i<n;i++)

{

cout<<arr[i]<<" ";

}

return 0;

}

output:

Sorted array is
0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

1 2	Sorted array is 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Tuts:

Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

Bucket Sort

Harumanchi Book implementation:

#include <stdio.h>
#include <stdlib.h>



int max(int a[],int n)
{
    int max=0,i;
    for(i=0; i<n; i++)
    {
        if(a[i]>max)
        {
            max=a[i];
        }
    }

    return max;
}




void bucket_sort(int a[],int n)
{
    int bucket=max(a,n);
    int b[bucket],i,k,j=-1;


    for(i=0; i<=bucket; i++)
        b[i]=0;




    for(i=0; i<n; i++)
    {
        b[a[i]]=b[a[i]]+1;
    }




    for(i=0; i<=bucket; i++)
    {
        for(k=b[i]; k>0; --k)
        {
            a[++j]=i;
        }
    }


}

int main()
{
    int i;


   // scanf("%d",&n);
    int arr[]={78,17,39,26,72,94,21,12,23,68};
    int n=sizeof(arr)/sizeof(arr[0]);


    bucket_sort(arr,n);

    for(i=0; i<n; i++)

        printf(" %d",arr[i]);

    return 0;
}

#include <stdio.h>

#include <stdlib.h>

int max(int a[],int n)

{

int max=0,i;

for(i=0; i<n; i++)

{

if(a[i]>max)

{

max=a[i];

}

return max;

}

void bucket_sort(int a[],int n)

{

int bucket=max(a,n);

int b[bucket],i,k,j=-1;

for(i=0; i<=bucket; i++)

b[i]=0;

for(i=0; i<n; i++)

{

b[a[i]]=b[a[i]]+1;

}

for(i=0; i<=bucket; i++)

{

for(k=b[i]; k>0; --k)

{

a[++j]=i;

}

int main()

{

int i;

// scanf("%d",&n);

int arr[]={78,17,39,26,72,94,21,12,23,68};

int n=sizeof(arr)/sizeof(arr[0]);

bucket_sort(arr,n);

for(i=0; i<n; i++)

printf(" %d",arr[i]);

return 0;

}

output:

 12 17 21 23 26 39 68 72 78 94

1	12 17 21 23 26 39 68 72 78 94

Time and Space complexity: O(n)

Leave a comment

Posted in Bucket Sort

Radix Sort

Posted on July 7, 2017 | Leave a comment

best video:

pseudocode:

Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        for i = 0 to n do
         count[key of(A[i]) in pass j]++
 
        for k = 1 to 10 do
         count[k] = count[k] + count[k-1]
 
        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--
 
        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]
 
    end for(j)
end func

Radix-Sort(A, d)

//It works same as counting sort for d number of passes.

//Each key in A[1..n] is a d-digit integer.

//(Digits are numbered 1 to d from right to left.)

for j = 1 to d do

//A[]-- Initial Array to Sort

int count[10] = {0};

//Store the count of "keys" in count[]

//key- it is number at digit place j

for i = 0 to n do

count[key of(A[i]) in pass j]++

for k = 1 to 10 do

count[k] = count[k] + count[k-1]

//Build the resulting array by checking

//new position of A[i] from count[k]

for i = n-1 downto 0 do

result[ count[key of(A[i])] ] = A[j]

count[key of(A[i])]--

//Now main array A[] contains sorted numbers

//according to current digit place

for i=0 to n do

A[i] = result[i]

end for(j)

end func

implementation: (I need to clear the radix sort part later..took help to implement)

// C implementation of Radix Sort
#include<bits/stdc++.h>

// This  function gives maximum value in array[]
int getMax(int A[], int n)
{
    int i;
    int max = A[0];
    for (i = 1; i < n; i++){
        if (A[i] > max)
            max = A[i];
    }
    return max;
}

// Main Radix Sort sort function
void radixSort(int A[], int n)
{
    int i,digitPlace = 1;
    int result[n]; // resulting array
    // Find the largest number to know number of digits
    int largestNum = getMax(A, n);


    //we run loop until we reach the largest digit place
    while(largestNum/digitPlace >0){

        int count[10] = {0};
         //Store the count of "keys" or digits in count[]
        for (i = 0; i < n; i++)
            count[ (A[i]/digitPlace)%10 ]++;

        // Change count[i] so that count[i] now contains actual
        //  position of this digit in result[]
        //  Working similar to the counting sort algorithm
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the resulting array
        for (i = n - 1; i >= 0; i--)
        {
            result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
            count[ (A[i]/digitPlace)%10 ]--;
        }

        // Now main array A[] contains sorted
        // numbers according to current digit place
        for (i = 0; i < n; i++)
            A[i] = result[i];

            // Move to next digit place
            digitPlace *= 10;
    }
}

// Function to print an array
void printArray(int A[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    printf("%d ", A[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int a[] = {432,312,304,310,123,124};
    int n = sizeof(a)/sizeof(a[0]);
    printf("Unsorted Array: ");
    printArray(a, n);

    radixSort(a, n);

    printf("Sorted Array: ");
    printArray(a, n);
    return 0;
}

// C implementation of Radix Sort

#include<bits/stdc++.h>

// This function gives maximum value in array[]

int getMax(int A[], int n)

{

int i;

int max = A[0];

for (i = 1; i < n; i++){

if (A[i] > max)

max = A[i];

}

return max;

}

// Main Radix Sort sort function

void radixSort(int A[], int n)

{

int i,digitPlace = 1;

int result[n]; // resulting array

// Find the largest number to know number of digits

int largestNum = getMax(A, n);

//we run loop until we reach the largest digit place

while(largestNum/digitPlace >0){

int count[10] = {0};

//Store the count of "keys" or digits in count[]

for (i = 0; i < n; i++)

count[ (A[i]/digitPlace)%10 ]++;

// Change count[i] so that count[i] now contains actual

// position of this digit in result[]

// Working similar to the counting sort algorithm

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

// Build the resulting array

for (i = n - 1; i >= 0; i--)

{

result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];

count[ (A[i]/digitPlace)%10 ]--;

}

// Now main array A[] contains sorted

// numbers according to current digit place

for (i = 0; i < n; i++)

A[i] = result[i];

// Move to next digit place

digitPlace *= 10;

}

// Function to print an array

void printArray(int A[], int n)

{

int i;

for (i = 0; i < n; i++)

printf("%d ", A[i]);

printf("\n");

}

// Driver program to test above functions

int main()

{

int a[] = {432,312,304,310,123,124};

int n = sizeof(a)/sizeof(a[0]);

printf("Unsorted Array: ");

printArray(a, n);

radixSort(a, n);

printf("Sorted Array: ");

printArray(a, n);

return 0;

}

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number

Leave a comment

Posted in Pore Abar Bujhbo, Radix Sort

Counting Sort

Posted on July 7, 2017 | Leave a comment

Algo:

COUNTING-SORT(A,B,k)
 
1. let C[0..k] be a new array
 
2. for i = 0 to k
 
3. 		C[i] = 0
 
4. for j = 1 to A.length
 
5. 		C[A[j]] = C[A[j]] + 1
 
6. // C[i] now contains the number of elements equal to i .
 
7. for i = 1 to k
 
8. 		C[i] = C[i] + C[i - 1]
 
9. // C[i] now contains the number of elements less than or equal to i .
 
10.for j = A.length downto 1
 
11.		B[C[A[j]]] = A[j]
 
12.		C[A[j]] = C[A[j]] - 1

COUNTING-SORT(A,B,k)

1. let C[0..k] be a new array

2. for i = 0 to k

3. C[i] = 0

4. for j = 1 to A.length

5. C[A[j]] = C[A[j]] + 1

6. // C[i] now contains the number of elements equal to i .

7. for i = 1 to k

8. C[i] = C[i] + C[i - 1]

9. // C[i] now contains the number of elements less than or equal to i .

10.for j = A.length downto 1

11. B[C[A[j]]] = A[j]

12. C[A[j]] = C[A[j]] - 1

Implemented Code:

#include<bits/stdc++.h>
using namespace std;
void countingSort(int a[],int k,int n)
{
    int i,j;
    int b[15],c[100];
    for(i=0;i<=k;i++)
        c[i]=0;
    for(j=1;j<=n;j++)
        c[a[j]]=c[a[j]]+1;
    for(i=1;i<=k;i++)
        c[i]=c[i]+c[i-1];
    for(j=n;j>=1;j--)
    {
        b[c[a[j]]]=a[j];
        c[a[j]]=c[a[j]]-1;
    }
    cout<<"Sorted Array is:"<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<" ";
        cout<<b[i];
    }
}
int main()
{

    int i,k=9; //k means maximum value in an array
  
    int A[]={5,2,9,5,2,3,5};
    int n=sizeof(A)/sizeof(A[0]);
    countingSort(A,k,n);

return 0;
}

#include<bits/stdc++.h>

using namespace std;

void countingSort(int a[],int k,int n)

{

int i,j;

int b[15],c[100];

for(i=0;i<=k;i++)

c[i]=0;

for(j=1;j<=n;j++)

c[a[j]]=c[a[j]]+1;

for(i=1;i<=k;i++)

c[i]=c[i]+c[i-1];

for(j=n;j>=1;j--)

{

b[c[a[j]]]=a[j];

c[a[j]]=c[a[j]]-1;

}

cout<<"Sorted Array is:"<<endl;

for(i=1;i<=n;i++)

{

cout<<" ";

cout<<b[i];

}

int main()

{

int i,k=9; //k means maximum value in an array

int A[]={5,2,9,5,2,3,5};

int n=sizeof(A)/sizeof(A[0]);

countingSort(A,k,n);

return 0;

}

Reference:
http://scanftree.com/Data_Structure/Counting-sort

Counting Sort in C

CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

Leave a comment

Posted in Counting Sort, Quicksort, Sorting

Binary Search Tree: Successor in Inorder Traversal

Posted on July 6, 2017 | Leave a comment

code:

/* C++ program to find Inorder successor in a BST */
#include<bits/stdc++.h>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
	if(root == NULL) return NULL;
	else if(root->data == data) return root;
	else if(root->data < data) return Find(root->right,data);
	else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
	if(root == NULL) return NULL;
	while(root->left != NULL)
		root = root->left;
	return root;
}

//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
	// Search the Node - O(h)
	struct Node* current = Find(root,data);
	if(current == NULL) return NULL;
	if(current->right != NULL) {  //Case 1: Node has right subtree
		return FindMin(current->right); // O(h)
	}
	else {   //Case 2: No right subtree  - O(h)
		struct Node* successor = NULL;
		struct Node* ancestor = root;
		while(ancestor != current) {
			if(current->data < ancestor->data) {
				successor = ancestor; // so far this is the deepest node for which current node is in left
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;
		}
		return successor;
	}
}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;

	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); 
        root = Insert(root,10);
	root = Insert(root,3); 
        root = Insert(root,4);
	root = Insert(root,1); 
        root = Insert(root,11);

	//Print Nodes in Inorder
	cout<<"Inorder Traversal: ";
	Inorder(root);
	cout<<"\n";

	// Find Inorder successor of some node.
	struct Node* successor = Getsuccessor(root,1);
	if(successor == NULL) cout<<"No successor Found\n";
	else
    cout<<"Successor is "<<successor->data<<"\n";
}

/* C++ program to find Inorder successor in a BST */

#include<bits/stdc++.h>

using namespace std;

struct Node {

int data;

struct Node *left;

struct Node *right;

};

//Function to find some data in the tree

Node* Find(Node*root, int data) {

if(root == NULL) return NULL;

else if(root->data == data) return root;

else if(root->data < data) return Find(root->right,data);

else return Find(root->left,data);

}

//Function to find Node with minimum value in a BST

struct Node* FindMin(struct Node* root) {

if(root == NULL) return NULL;

while(root->left != NULL)

root = root->left;

return root;

}

//Function to find Inorder Successor in a BST

struct Node* Getsuccessor(struct Node* root,int data) {

// Search the Node - O(h)

struct Node* current = Find(root,data);

if(current == NULL) return NULL;

if(current->right != NULL) { //Case 1: Node has right subtree

return FindMin(current->right); // O(h)

}

else { //Case 2: No right subtree - O(h)

struct Node* successor = NULL;

struct Node* ancestor = root;

while(ancestor != current) {

if(current->data < ancestor->data) {

successor = ancestor; // so far this is the deepest node for which current node is in left

ancestor = ancestor->left;

}

else

ancestor = ancestor->right;

}

return successor;

}

//Function to visit nodes in Inorder

void Inorder(Node *root) {

if(root == NULL) return;

Inorder(root->left); //Visit left subtree

printf("%d ",root->data); //Print data

Inorder(root->right); // Visit right subtree

}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,char data) {

if(root == NULL) {

root = new Node();

root->data = data;

root->left = root->right = NULL;

}

else if(data <= root->data)

root->left = Insert(root->left,data);

else

root->right = Insert(root->right,data);

return root;

}

int main() {

/*Code To Test the logic

Creating an example tree

/ \

3 10

/ \ \

1 4 11

Node* root = NULL;

root = Insert(root,5);

root = Insert(root,10);

root = Insert(root,3);

root = Insert(root,4);

root = Insert(root,1);

root = Insert(root,11);

//Print Nodes in Inorder

cout<<"Inorder Traversal: ";

Inorder(root);

cout<<"\n";

// Find Inorder successor of some node.

struct Node* successor = Getsuccessor(root,1);

if(successor == NULL) cout<<"No successor Found\n";

else

cout<<"Successor is "<<successor->data<<"\n";

}

Leave a comment

Posted in Binary Search Tree, Tree

Delete a node in Binary Search Tree

Posted on July 5, 2017 | Leave a comment

code:

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    struct Node* left;
    struct Node* right;
};

Node* FindMin(Node* root)
{
    while(root->left!=NULL)
        root=root->left;
    return root;
}

//Function to search a delete value from tree
struct Node* Delete(struct Node *root, int data)
{

    if(root==NULL)
        return root;
    else if(data<root->data)
        root->left=Delete(root->left,data);
    else if(data>root->data)
        root->right=Delete(root->right,data);
    else{
        //case 1: No child
        if(root->left==NULL && root->right==NULL)
        {
            delete root;
            root=NULL;
        }
        //case 2: one child
        else if(root->left==NULL)
        {
            struct Node* temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL)
        {
            struct Node* temp=root;
            root=root->left;
            delete temp;
        }
        //case 3: 2 children
        else{
            struct Node * temp=FindMin(root->right);
            root->data=temp->data;
            root->right=Delete(root->right, temp->data);
        }

    }
return root;
}

//function to visit nodes in inorder
void Inorder(Node* root)
{
    if(root==NULL)
          return;
    Inorder(root->left); //visit left subtree
    printf("%d ",root->data); //print data
    Inorder(root->right); //visit right subtree
}


Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}

int main()
{
    Node *root=NULL;
    root=Insert(root,5);
    root=Insert(root,10);
    root=Insert(root,3);
    root=Insert(root,4);
    root=Insert(root,1);
    root=Insert(root,11);

    root=Delete(root,5);

    //Print Nodes in Inorder
    cout<<"Inorder: ";
    Inorder(root);
    cout<<"\n";

}

100

101

#include<bits/stdc++.h>

using namespace std;

struct Node{

int data;

struct Node* left;

struct Node* right;

};

Node* FindMin(Node* root)

{

while(root->left!=NULL)

root=root->left;

return root;

}

//Function to search a delete value from tree

struct Node* Delete(struct Node *root, int data)

{

if(root==NULL)

return root;

else if(data<root->data)

root->left=Delete(root->left,data);

else if(data>root->data)

root->right=Delete(root->right,data);

else{

//case 1: No child

if(root->left==NULL && root->right==NULL)

{

delete root;

root=NULL;

}

//case 2: one child

else if(root->left==NULL)

{

struct Node* temp=root;

root=root->right;

delete temp;

}

else if(root->right==NULL)

{

struct Node* temp=root;

root=root->left;

delete temp;

}

//case 3: 2 children

else{

struct Node * temp=FindMin(root->right);

root->data=temp->data;

root->right=Delete(root->right, temp->data);

}

return root;

}

//function to visit nodes in inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //visit left subtree

printf("%d ",root->data); //print data

Inorder(root->right); //visit right subtree

}

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

Node *root=NULL;

root=Insert(root,5);

root=Insert(root,10);

root=Insert(root,3);

root=Insert(root,4);

root=Insert(root,1);

root=Insert(root,11);

root=Delete(root,5);

//Print Nodes in Inorder

cout<<"Inorder: ";

Inorder(root);

cout<<"\n";

}

Leave a comment

Posted in Binary Search Tree, Tree

Traversal in Binary Search Tree

Posted on July 4, 2017 | Leave a comment

Height of a binary tree:

Level Order BFS in Binary Search Tree:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void LevelOrder(Node *root)
{
    if(root==NULL)
        return;
    queue<Node*> Q;
    Q.push(root);
    //while there is at least one discovered node
    while(!Q.empty())
    {
        Node* current=Q.front();
        Q.pop();
        cout<<current->data<<" ";
        if(current->left!=NULL)
            Q.push(current->left);
        if(current->right!=NULL)
            Q.push(current->right);
    }
}
//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');
    LevelOrder(root);
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void LevelOrder(Node *root)

{

if(root==NULL)

return;

queue<Node*> Q;

Q.push(root);

//while there is at least one discovered node

while(!Q.empty())

{

Node* current=Q.front();

Q.pop();

cout<<current->data<<" ";

if(current->left!=NULL)

Q.push(current->left);

if(current->right!=NULL)

Q.push(current->right);

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

LevelOrder(root);

}

output:

M B Q A C Z

1	M B Q A C Z

DFS in Preorder, Inorder, Postorder:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void Preorder(struct Node* root){

    if(root==NULL)
        return;
    printf("%c ",root->data);//print data
    Preorder(root->left); //visit left subtree
    Preorder(root->right); //Visit right subtree
}

//function to visit nodes in Inorder
void Inorder(Node* root)
{
    if(root==NULL)
        return;
    Inorder(root->left); //Visit left subtree
    printf("%c ",root->data); //Print  data
    Inorder(root->right); //Visit right subtree
}

void Postorder(Node* root)
{
    if(root==NULL)
        return;
    Postorder(root->left); //visit left subtree
    Postorder(root->right); //visit right subtree
    printf("%c ",root->data); //print data


}


//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');

    //Print nodes in preorder
    cout<<"Preorder: ";
    Preorder(root);
    cout<<endl;
    //Print nodes in in inorder
    cout<<"Inorder:  ";
    Inorder(root);
    cout<<endl;
    //Print Nodes in postorder
    cout<<"Postorder: ";
    Postorder(root);
    cout<<endl;
    return 0;
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void Preorder(struct Node* root){

if(root==NULL)

return;

printf("%c ",root->data);//print data

Preorder(root->left); //visit left subtree

Preorder(root->right); //Visit right subtree

}

//function to visit nodes in Inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //Visit left subtree

printf("%c ",root->data); //Print data

Inorder(root->right); //Visit right subtree

}

void Postorder(Node* root)

{

if(root==NULL)

return;

Postorder(root->left); //visit left subtree

Postorder(root->right); //visit right subtree

printf("%c ",root->data); //print data

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

//Print nodes in preorder

cout<<"Preorder: ";

Preorder(root);

cout<<endl;

//Print nodes in in inorder

cout<<"Inorder: ";

Inorder(root);

cout<<endl;

//Print Nodes in postorder

cout<<"Postorder: ";

Postorder(root);

cout<<endl;

return 0;

}

output:

Preorder: M B A C Q Z
Inorder:  A B C M Q Z
Postorder: A C B Z Q M

Preorder: M B A C Q Z

Inorder: A B C M Q Z

Postorder: A C B Z Q M

Leave a comment

Posted in Binary Search Tree, Tree

Binary Search Tree

Posted on July 4, 2017 | Leave a comment

youtube :

code:

#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode
{
    int data;
    BstNode* left;
    BstNode* right;
};
//Function to create new Node in heap
BstNode* GetNewNode(int data)
{
    BstNode* newNode=new BstNode();
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    return newNode;
}
//To search an element in BST return true if element is found
bool Search(BstNode* root, int data)
{
    if(root==NULL)
        return false;
    else if(root->data==data)
        return true;
    else if(data<=root->data)
        return Search(root->left,data);
    else
        return Search(root->right,data);
}
//TO insert data in BST, return address of root node
BstNode* Insert(BstNode* root, int data)
{
    if(root==NULL) //empty tree
    {
        root=GetNewNode(data);
    }
    //if data to be inserted is lesser, insert it in left subtree
    else if(data<=root->data)
    {
        root->left=Insert(root->left,data);
    }
    //else, insert in right subtree
    else
    {
        root->right=Insert(root->right,data);
    }
    return root;
}

int main()
{
    BstNode* root=NULL;//creating an empty tree
    /* Code to test the logic */
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,20);
    root=Insert(root,25);
    root=Insert(root,8);
    root=Insert(root,12);
    //asking user to enter a number
    int number;
    cout<<"Enter number to be searched:\n";
    cin>>number;
    //If number is found, print "FOUND"
    if(Search(root,number)==true)
        cout<<"Found\n";
    else
        cout<<"Not Found\n";
    return 0;
}

#include<iostream>

using namespace std;

//Definition of Node for Binary search tree

struct BstNode

{

int data;

BstNode* left;

BstNode* right;

};

//Function to create new Node in heap

BstNode* GetNewNode(int data)

{

BstNode* newNode=new BstNode();

newNode->data=data;

newNode->left=newNode->right=NULL;

return newNode;

}

//To search an element in BST return true if element is found

bool Search(BstNode* root, int data)

{

if(root==NULL)

return false;

else if(root->data==data)

return true;

else if(data<=root->data)

return Search(root->left,data);

else

return Search(root->right,data);

}

//TO insert data in BST, return address of root node

BstNode* Insert(BstNode* root, int data)

{

if(root==NULL) //empty tree

{

root=GetNewNode(data);

}

//if data to be inserted is lesser, insert it in left subtree

else if(data<=root->data)

{

root->left=Insert(root->left,data);

}

//else, insert in right subtree

else

{

root->right=Insert(root->right,data);

}

return root;

}

int main()

{

BstNode* root=NULL;//creating an empty tree

/* Code to test the logic */

root=Insert(root,15);

root=Insert(root,10);

root=Insert(root,20);

root=Insert(root,25);

root=Insert(root,8);

root=Insert(root,12);

//asking user to enter a number

int number;

cout<<"Enter number to be searched:\n";

cin>>number;

//If number is found, print "FOUND"

if(Search(root,number)==true)

cout<<"Found\n";

else

cout<<"Not Found\n";

return 0;

}

Leave a comment

Posted in Binary Search Tree, Tree

Heap Sort

Posted on June 29, 2017 | Leave a comment

Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap

Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node

pseudocode:

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i,n)

Heapify(A as array, i as int, n as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else 
        max = i

    if (right<=n) and (A[right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)

Heapsort(A as array)

BuildHeap(A)

for i = n to 1

swap(A[1], A[i])

n = n - 1

Heapify(A, 1)

BuildHeap(A as array)

n = elements_in(A)

for i = floor(n/2) to 1

Heapify(A,i,n)

Heapify(A as array, i as int, n as int)

left = 2i

right = 2i+1

if (left <= n) and (A[left] > A[i])

max = left

else

max = i

if (right<=n) and (A[right] > A[max])

max = right

if (max != i)

swap(A[i], A[max])

Heapify(A, max)

source:
http://www.algorithmist.com/index.php/Heap_sort

Implemented code:

//this is descending order max-heapify

#include<bits/stdc++.h>
using namespace std;
//swapping numbers using call by reference
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}

//this max heapify ensure that child node is always smaller than the parent node
MaxHeapify(int ary[],int n,int i){
    int largest=i;
int    left=2*i+1;
int     right=2*i+2;
    if(left<n && ary[left]>ary[largest])
    {
        largest=left;
    }
    if(right<n && ary[right]>ary[largest])
    {
        largest=right;
    }
    if(largest!=i)
    {
        swaps(&ary[i],&ary[largest]);
        MaxHeapify(ary,n,largest);
    }
}

//building heap
void BuildHeap(int ary[],int n)
{
    int i;
    for(i=floor(n/2)-1;i>=0;i--){
        MaxHeapify(ary,n,i);
    }
}

//heapSort function sorting the array
void heapSort(int ary[],int n)
{
    BuildHeap(ary,n);
    for(int i=n-1;i>0;i--){
           swaps(&ary[0],&ary[i]);
           int heap_size=i;
           MaxHeapify(ary,heap_size,0);
    }
}
//utility function
void printAry(int ary[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<ary[i]<<" ";
    }
}
//driver program
int main(){
    int ary[]={40,60,10,20,50,30};
    int n=sizeof(ary)/sizeof(ary[0]);
    heapSort(ary,n);
    cout<<"Sorted array:";
    printAry(ary,n);

}

//this is descending order max-heapify

#include<bits/stdc++.h>

using namespace std;

//swapping numbers using call by reference

int swaps(int *p,int *q)

{

int temp=*q;

*q=*p;

*p=temp;

}

//this max heapify ensure that child node is always smaller than the parent node

MaxHeapify(int ary[],int n,int i){

int largest=i;

int left=2*i+1;

int right=2*i+2;

if(left<n && ary[left]>ary[largest])

{

largest=left;

}

if(right<n && ary[right]>ary[largest])

{

largest=right;

}

if(largest!=i)

{

swaps(&ary[i],&ary[largest]);

MaxHeapify(ary,n,largest);

}

//building heap

void BuildHeap(int ary[],int n)

{

int i;

for(i=floor(n/2)-1;i>=0;i--){

MaxHeapify(ary,n,i);

}

//heapSort function sorting the array

void heapSort(int ary[],int n)

{

BuildHeap(ary,n);

for(int i=n-1;i>0;i--){

swaps(&ary[0],&ary[i]);

int heap_size=i;

MaxHeapify(ary,heap_size,0);

}

//utility function

void printAry(int ary[],int n)

{

for(int i=0;i<n;i++)

{

cout<<ary[i]<<" ";

}

//driver program

int main(){

int ary[]={40,60,10,20,50,30};

int n=sizeof(ary)/sizeof(ary[0]);

heapSort(ary,n);

cout<<"Sorted array:";

printAry(ary,n);

}

output:

Sorted array:10 20 30 40 50 60

1	Sorted array:10 20 30 40 50 60

Took help from these two links:
http://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/
http://www.geeksforgeeks.org/heap-sort/

Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)

Leave a comment

Posted in Algorithm, Heap Sort