Binary Trees

Important Questions on Binary Trees

Question 1  Find diameter of a binary tree 

#include<iostream>

#include<stdio.h>

#include<queue>

#include<math.h>

using namespace std;

struct bstNode{

int data;

bstNode *left;

bstNode *right;

};

bstNode *getNewNode(int d){

bstNode *start=new bstNode();

start->data=d;

start->left=NULL;

start->right=NULL;

return start;

}

bstNode *insert(bstNode *root,int d){

if(root==NULL){

root=getNewNode(d);

return root;

}

else if(root->data>=d){

root->left=insert(root->left,d);

return root;

}

else if(root->data<d){

root->right=insert(root->right,d);

return root;

}

}

int height(bstNode *root){

int leftheight,rightheight;

if(root==NULL){

return -1;

}

leftheight=height(root->left);

rightheight=height(root->right);;

return max(leftheight,rightheight)+1;

}

int count=0;

void levelOrder(bstNode *root,int space){

queue<bstNode *> q;

q.push(root);

count++;

int i=0;

int x=space;

while(!q.empty()){

x=x/2;

bstNode *current=q.front();

for(i=0;i<x;i++){

cout<<"  ";

}

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

count--;

for(i=0;i<x;i++){

cout<<"  ";

}

if(current->left!=NULL){

q.push(current->left);

}

if(current->right!=NULL){

q.push(current->right);

}

q.pop();

if(count==0){

count=q.size();

cout<<endl;

}

}

cout<<"\n";

for(i=0;i<x;i++){

cout<<"  ";

}

}

int Diameter(bstNode * root, int& h){

int hl=0,hr=0,dl,dr,dia;

if(root==NULL){

h=0;

return 0;

}

dl=Diameter(root->left,hl);

dr=Diameter(root->right,hr);

if(hl>hr){

h=hl+1;

}else{

h=hr+1;

}

h=max(hl,hr)+1;

int x=hl+hr+1,m;

//cout<<"\nRoot -> Data"<<root->data<<"  Hl = "<<hl<<"    Hr = "<<hr<<"  DL = "<<dl<<"  DR = "<<dr;

if(dl>dr){

m=dl;

}else{

m=dr;

}

if(m>x){

dia=m;

}else{

dia=x;

}

return dia;

}

main(){

bstNode *root;

int c=4;

root=NULL;

root=insert(root,30);

root=insert(root,15);

root=insert(root,40);

root=insert(root,35);

root=insert(root,45);

root=insert(root,10);

root=insert(root,20);

root=insert(root,9);

root=insert(root,12);

root=insert(root,13);

root=insert(root,21);

root=insert(root,22);

root=insert(root,23);

root=insert(root,24);

root=insert(root,50);

root=insert(root,60);

root=insert(root,70);

//levelOrder(root,x);

cout<<"\nDiameter is = "<<Diameter(root,c);

}

Question 2 Given a Binary tree check if it is balanced i.e. depth of the left and right subtrees of every node differ by 1 or less 

#include<iostream>

#include<stdio.h>

#include<queue>

#include<math.h>

using namespace std;

struct bstNode{

int data;

bstNode *left;

bstNode *right;

};

bstNode *getNewNode(int d){

bstNode *start=new bstNode();

start->data=d;

start->left=NULL;

start->right=NULL;

return start;

}

bstNode *insert(bstNode *root,int d){

if(root==NULL){

root=getNewNode(d);

return root;

}

else if(root->data>=d){

root->left=insert(root->left,d);

return root;

}

else if(root->data<d){

root->right=insert(root->right,d);

return root;

}

}

int height(bstNode *root){

int leftheight,rightheight;

if(root==NULL){

return -1;

}

leftheight=height(root->left);

rightheight=height(root->right);;

return max(leftheight,rightheight)+1;

}

bool checkBST(bstNode *root, int& h){

int hl=0, hr=0, diff, max;

bool x1, x2;

if(root==NULL){

h=-1;

return 1;

}

x1=checkBST(root->left,hl);

x2=checkBST(root->right,hr);

if(hl>=hr){

diff=hl-hr;

max=hl;

}else{

diff=hr-hl;

max=hr;

}

if((x1&x2)&&(diff<=1)){

h=max+1;

return 1;

}else{

return 0;

}

}

main(){

bstNode *root;

int h=0;;

root=NULL;

root=insert(root,30);

root=insert(root,15);

root=insert(root,40);

root=insert(root,35);

root=insert(root,45);

root=insert(root,10);

root=insert(root,20);

root=insert(root,9);

root=insert(root,12);

root=insert(root,8);

root=insert(root,13);

root=insert(root,21);

root=insert(root,50);

/* root=insert(root,22);

root=insert(root,23);

root=insert(root,24);

root=insert(root,50);

root=insert(root,60);

root=insert(root,70);

*/

bool x=checkBST(root,h);

if(x){

cout<<"\nTree is balanced";

}else{

cout<<"\nTree is NOT balanced";

}

}

Question 3 You have a binary tree with non-negative numeric values stored in its nodes, you need to find out the maximum possible sum of all the nodes. Selection of nodes for the sum follows following constraint:  If you have selected any node for the sum, you can not select its immediate parent and its children for sum.

#include<iostream>
#include<stdio.h>
#include<queue>
#include<math.h>
using namespace std;

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

bstNode *getNewNode(int d){
bstNode *start=new bstNode();
start->data=d;
start->left=NULL;
start->right=NULL;
return start;
}

bstNode *insert(bstNode *root,int d){
if(root==NULL){
root=getNewNode(d);
return root;
}
else if(root->data>=d){
root->left=insert(root->left,d);
return root;
}
else if(root->data<d){
root->right=insert(root->right,d);
return root;
}
}
struct xy{
int x, y;
};
xy max_sum(bstNode *root){
xy i,i1,i2;
if(root==NULL){
i.x=0;
i.y=0;
return i;
}
i1=max_sum(root->left);
i2=max_sum(root->right);
i.x=i1.y+i2.y+root->data;
i.y=i1.x+i2.x;
return i;
}
main(){
bstNode *root;
int h=0;;
root=NULL;
root=insert(root,1000);
root=insert(root,1001);
root=insert(root,100);
root=insert(root,100);

xy instance =max_sum(root);
int x=instance.x,y=instance.y,m;
m=max(x, y);
cout<<"\nmax sum is = "<<m;

}

Trees Data Structure

Generic Trees  implementation in C/C++

Why Tree?
Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.

One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer:

So lets get started with trees

First of all lets see a tree data structure in a general form later on we would see specific Trees like Binary Tree, Binary Search Tree, AVL Trees etc.
A Tree is a Non-linear data structure, in which there is Parent node and that parent node has any No. of children                                                      

now lets see a program:-

The following Program includes Build Tree function, Max Depth, Max Element and Print(BFS) function

#include<iostream>

#include<queue>

using namespace std;

struct node{

int data;

int childcount;

node **child;

};

node *BuildTree(){

node *root=new node;

cout<<"enter the data of root\t";

cin>>root->data;

queue <node *> q;

q.push(root);

while(!q.empty()){

node *temp=q.front();

cout<<"\nenter no of childs of node whith data  "<<temp->data << endl;

cin>>temp->childcount;

temp->child=new node*[temp->childcount];

for(int i=0;i<temp->childcount;i++){

temp->child[i]=new node;

cout<<"\nEnter data  ";

cin >> temp->child[i]->data;

q.push(temp->child[i]);

}

q.pop();

}

return root;

}

void printTree(node *root){

node* temp=root;

queue <node *> q;

q.push(root);

while(!q.empty()){

node *temp=q.front();

cout<<"\nnode whith data  "<<temp->data << " Has "<<temp->childcount << " childern"<<endl;

for(int i=0;i<temp->childcount;i++){

node *c;

c=temp->child[i];

q.push(c);

}

cout <<"\n";

q.pop();

}

}

int max_element(node *root){

queue <node *> q;

q.push(root);

int max=root->data;

while(!q.empty()){

node *temp=q.front();

if(temp->data>max){

max=temp->data;

}

for(int i=0;i<temp->childcount;i++){

node *c;

c=temp->child[i];

q.push(c);

}

q.pop();

}

return max;

}

int max_depth(node *root){

if(root->childcount==0){

return 0;

}

int depth=-1,tempDepth;

for(int i=0;i<root->childcount;i++){

tempDepth = max_depth(root->child[i]);

if(depth<tempDepth){

depth=tempDepth;

}

}

return depth+1;

}

main(){

node *root=BuildTree();

printTree(root);

int depth=max_depth(root);

cout<<"\nDepth is "<<depth;

cout<<"\nMax element is = "<<max_element(root);

}

Reverse Of Singly Linked List

Three methods are given Below

#include<iostream>
using namespace std;
struct node{
int data;
node *next;
}*tt,*bt;
int count=0;
void insert_head(node **pointerToStart,node **pointerToTail,int n){
node *temp=new node;
temp->data=n;
if(*pointerToStart==NULL){
(*temp).next=*pointerToStart;
*pointerToStart=temp;
*pointerToTail=temp;
count++;
}
else{
(*temp).next=*pointerToStart;
*pointerToStart=temp;
count++;
}

}

void print_list(node** pointerToStart){
node* temp=*pointerToStart;
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<<"NULL";
}

/*   comments starts
void reverse(node** pointerTostart,node *p){
if(p->next==NULL){
*pointerTostart=p;
return;
}
reverse(&*pointerTostart,p->next);
node*q=p->next;
q->next=p;
p->next=NULL;

}

node *reverse(node **pointerToNode){
node* head;

if((*pointerToNode)->next==NULL){

head=*pointerToNode;
return head;
}
node *q=(*pointerToNode)->next;
node *p=*pointerToNode;
head=reverse(&q);
node *temp=p->next;
temp->next=p;
p->next=NULL;
return head;
}
comment ends  */
void reverse(node **headRef){
if((*headRef)==NULL){
return;
}
node *rest = (*headRef)->next, *first=*headRef;
if(rest==NULL){
return;
}

reverse(&rest);
first->next->next=first;
first->next=NULL;
(*headRef)=rest;
}
main(){

node *start=NULL,*tail=NULL;

for(int i=1;i<10;i++){
insert_head(&start,&tail,i);
}
print_list(&start);
//reverse(&start,start);
reverse(&start);
cout<<"\n";
print_list(&start);
}

Some Advanced Link List Concept

XOR Doubly Link List

An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory efficient version of Doubly Linked List can be created using only one space for address field with every node. This memory efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the list uses bitwise XOR operation to save space for one address. In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

Consider the above Doubly Linked List. Following are the Ordinary and XOR (or Memory Effiecient) representations of the Doubly Linked List.

Ordinary Representation:
Node A:
prev = NULL, next = add(B) // previous is NULL and next is address of B

Node B:
prev = add(A), next = add(C) // previous is address of A and next is address of C

Node C:
prev = add(B), next = add(D) // previous is address of B and next is address of D

Node D:
prev = add(C), next = NULL // previous is address of C and next is NULL

XOR List Representation:
Let us call the address variable in XOR representation npx (XOR of next and previous)

Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B

Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C

Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D

Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0

Traversal of XOR Linked List:
We can traverse the XOR list in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example when we are at node C, we must have address of B. XOR of add(B) and npx of C gives us the add(D). The reason is simple: npx(C) is “add(B) XOR add(D)”. If we do xor of npx(C) with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0″ which is “add(D)”. So we have the address of next node. Similarly we can traverse the list in backward direction.

Doubly Link List

Programs include Insertion and deletion function of Doubly Link List

#include<iostream>
using namespace std;

struct node{
int data;
node *next;
node *prev;
};
void insert_head(node **pointerToStart, int n){
cout<<"c 1";
node *temp=new node;
temp->data=n;
if(*pointerToStart==NULL){
temp->next=NULL;
temp->prev=NULL;
*pointerToStart=temp;
return; //  agar mein if vali contion hata huin to galt ata hai ans
}
temp->next=*pointerToStart;
temp->prev=NULL;
cout<<"c 2";
(*pointerToStart)->prev=temp;
cout<<"c 3";
*pointerToStart=temp;
cout<<"c 4";

cout<<"c 5";
}

void insert_tail(node **pointerToStart, int n){
node *temp=new node;
temp->data=n;
node *t=*pointerToStart;
if(*pointerToStart==NULL){
temp->next=NULL;
temp->prev=NULL;
*pointerToStart=temp;
return;
}
while(t->next!=NULL){
t=t->next;
}
t->next=temp;
temp->prev=t;
temp->next=NULL;
}
void print_list(node** pointerToStart){
node* temp=*pointerToStart;
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<<"NULL";
}
void del(node **pointerToStart, int n){
node *temp=*pointerToStart;

while(temp!=NULL){
if(temp->data==n){

if(temp->next==NULL&&temp->prev==NULL){
delete *pointerToStart;
*pointerToStart=NULL;
cout<<"\nNo deleted \n";
return;
}
else if(temp->next==NULL){
temp->prev->next=NULL;
cout<<"\nNo deleted \n";
return;
}
else if(temp->prev==NULL){
*pointerToStart=temp->next;
temp->next->prev=NULL;
cout<<"\nNo deleted \n";
return;
}
(temp->prev)->next=temp->next;
(temp->next)->prev=temp->prev;
delete temp;
cout<<"\nNo deleted \n";
return;
}
temp=temp->next;
}
cout<<"\nno not found";
return;
}
main(){

int d;
int t=1;
node *start=NULL,*tail=NULL;
while(t=1){
//cout<<"\n";
cout<<"\nPress 1 to add at head";
cout<<"\nPress 2 to add at tail";
//cout<<"\nPress 3 to search a no";
cout<<"\nPress 4 to print the list";
cout<<"\nPress 5 to delete";
cout<<"\nPress 6 to Buble Sort";
cout<<"\nPress 12 to exit\n";
int c;
cin>>c;
switch(c){
case 1 :
cout<<"enter data ";
cin >> d;
insert_head(&start,d);
break;

case 2 :
cout<<"enter data ";
cin >> d;
insert_tail(&start,d);
break;

case 3 :
cout<<"enter Number which you wana find ";
cin >> d;


break;

case 4 :
print_list(&start);
break;

case 5 :
cout<<"\nenter the no you wana delete  ";
cin>>d;
del(&start,d);
break;

case 6:
// bubleSort(&start);
print_list(&start);
case 12 :
t=0;

}
}
}

Singly Link List

A program of Singly link list which function such as Insertion At Head, Insertion At Tail, Bubble Sort, Find function, Delete function, Print function 




#include<iostream>
using namespace std;

struct node{
int data;
node *next;
};
int count=0;
void insert_head(node **pointerToStart,node **pointerToTail,int n){
node *temp=new node;
temp->data=n;
if(*pointerToStart==NULL){
(*temp).next=*pointerToStart;
*pointerToStart=temp;
*pointerToTail=temp;
count++;
}
else{
(*temp).next=*pointerToStart;
*pointerToStart=temp;
count++;
}

}

void insert_tail(node **pointerToStart,node **pointerToTail,int n){
node *temp=new node;
temp->data=n;
if(*pointerToStart==NULL){
(*temp).next=*pointerToStart;
*pointerToStart=temp;
*pointerToTail=temp;
count++;
}
else{
(*pointerToTail)->next=temp;
temp->next=NULL;
*pointerToTail=temp;
count++;
}

}

bool find(node** pointerToStart,int n){
node* temp=*pointerToStart;
if(*pointerToStart==NULL){
return false;
}
while(temp!=NULL){
if(temp->data==n){
return true;
}
temp=temp->next;
}
return false;
}

void del(node** pointerToStart,int n){
node *previous=NULL,*current=*pointerToStart;
if(find(pointerToStart,n)==false){
cout<<"\nNo is not present in the list\n";
}
else{
if((*pointerToStart)->data==n){
*pointerToStart=current->next;
delete current;
cout<<"\n No deleted\n";
return;
}
else{
while(current!=NULL){
if(current->data==n){
previous->next=current->next;
delete current;
cout<<"\n No deleted\n";
return;
}
previous=current;
current = current->next;

}
}
}
}

void print_list(node** pointerToStart){
node* temp=*pointerToStart;
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<<"NULL";
}

void bubleSort(node** pointerToStart){
int n=count;
node* temp,*current;
cout<<"\no of elements are = "<<n;
while(n--){

temp=*pointerToStart;
current=temp->next;
cout<<"\ncheck 1 ";
while(current!=NULL){
cout<<"\ncheck 2 ";
if(temp->data>temp->next->data){
int t=temp->data;
temp->data=temp->next->data;
temp->next->data=t;
}
temp=temp->next;
current=temp->next;
}

}
return;
}
main(){
int d;
int t=1;
node *start=NULL,*tail=NULL;
while(t=1){
//cout<<"\n";
cout<<"\nPress 1 to add at head";
cout<<"\nPress 2 to add at tail";
cout<<"\nPress 3 to search a no";
cout<<"\nPress 4 to print the list";
cout<<"\nPress 5 to delete";
cout<<"\nPress 6 to Buble Sort";
cout<<"\nPress 12 to exit\n";
int c;
cin>>c;
switch(c){
case 1 :
cout<<"enter data ";
cin >> d;
insert_head(&start,&tail,d);
break;

case 2 :
cout<<"enter data ";
cin >> d;
insert_tail(&start,&tail,d);
break;

case 3 :
cout<<"enter Number which you wana find ";
cin >> d;
if(find(&start,d)==true){
cout<<"\nNumber is present\n";
}
else{
cout<<"\nNumber is Not present\n";
}
break;

case 4 :
print_list(&start);
break;

case 5 :
cout<<"\nenter the no you wana delete  ";
cin>>d;
del(&start,d);
break;

case 6:
bubleSort(&start);
print_list(&start);
case 12 :
t=0;

}
}
}

Some basic Coding Problems

1. Implement merge, quick, insertion, selection, bubble sorts.  

Merge Sort

#include<iostream>

using namespace std;

int temp[1000];

void merge(int a[],int startIndex,int endIndex){

int mid=(startIndex+endIndex)/2;

int i,j,k;

i=startIndex;j=mid+1;k=0;

while(i<=mid&&j<=endIndex){

if(a[i]<a[j]){

temp[k]=a[i];  i++;k++;

}

else{

temp[k]=a[j];   j++;k++;

}

}

while(i<=mid){

temp[k]=a[i];     i++;k++;

}

while(j<=endIndex){

temp[k]=a[j];      j++;k++;

}

}

void mergesort(int a[],int startIndex,int endIndex){

if(startIndex<endIndex){

int mid=(startIndex + endIndex)/2;

mergesort(a,startIndex,mid);

mergesort(a,mid+1,endIndex);

merge(a,startIndex,endIndex);

}

}

main(){

int arr[100], n;

cin >> n;

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

cin >> arr[i];

}

mergesort(arr,0,n-1);

cout <<"\n";

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

cout << temp[i]<<"\t";

}

}

 quick Sort

#include<iostream>

using namespace std;

int partion(int arr[],int startIndex,int endIndex){

int pindex=startIndex+1;

int pivot=arr[startIndex];

int i;

for(i=startIndex+1;i<=endIndex;i++){

if(pivot>arr[i]){

swap(arr[i],arr[pindex]);

pindex++;

}

}

swap(arr[startIndex],arr[pindex-1]);

return pindex-1;

}

void quicksort(int arr[],int startIndex,int endIndex ){

if(startIndex>=endIndex){

return;

}

int x= partion(arr,startIndex,endIndex);

quicksort(arr,startIndex,x);

quicksort(arr,x+1,endIndex);

}

main(){

int n,arr[1000],i,j,k;

cin>>n;               //size of array

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

cin>>arr[i];

}

quicksort(arr,0,n-1);

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

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

}

}

Selection Sort

#include<iostream>

using namespace std;

void selectionSort(int arr[],int startIndex, int endIndex){

int temp=arr[0];

for(int i=0;i<=endIndex;i++){

int minIndex=i;

for(int j=i+1;j<=endIndex;j++){

if(arr[minIndex]>arr[j]){

minIndex=j;

}

}

swap(arr[i],arr[minIndex]);

}

}

main(){

int n,arr[1000],i,j,k;

cin>>n;               //size of array

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

cin>>arr[i];

}

selectionSort(arr,0,n-1);

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

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

}

}

Insertion Sort

#include<iostream>

using namespace std;

void shift(int arr[],int start,int hole){

int temp;

for(int i=hole;i>start;i--){

arr[i]=arr[i-1];

}

}

void insertionsort(int arr[],int endIndex){

int temp=0;

for(int i=1;i<=endIndex;i++){

int temp=arr[i];

int j=i-1;

while(arr[i]<arr[j]&&j>=0){

j--;

}

if(j==-1){

shift(arr,0,i);

arr[0]=temp;

}

else{

shift(arr,j+1,i);

arr[j+1]=temp;

}

}

}

main(){

int n,arr[1000],i,j,k;

cin>>n;               //size of array

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

cin>>arr[i];

}

insertionsort(arr,n-1);

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

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

}

}

2. Using the phone keypad return all possible words that can be produced given input  digits. e.g. 23 ­> “ad, ae, af, bd, be, bf, cd, ce, cf”

3. Given a input number in array form. Push all the zeroes to the end maintaining the  order of rest of elements.

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

main(){
int n,i,j=0,k=0,a1[100],h[100],*p1,*p2;

cin>>n;                              // size of array

for(i=0;i<n;i++){
cin>>a1[i];
if(a1[i]==0){
k++;
}
}

p1=&a1[0];
for(j=0,i=0;i<n;i++){
if(a1[i]==0){
p1++;
}
else{
a1[j]=*p1;
p1++;
j++;
}
}
for(i=j-1;i<n;i++){
a1[i]=0;
}
cout<<"\n";
for(i=0;i<n;i++){
cout<<a1[i]<<"\t";
}


}


4. Given a number find next palindrome number. e.g. 119 ­> 121

#include<iostream>
using namespace std;

bool palindrome(int n){
int arr[100],temp=n,i=0;
while(temp>0){
arr[i]=temp%10;
temp=temp/10;
i++;
}

int s=0,r=i-1;
while(s<r){

if(arr[s]!=arr[r]){
return false;
}
s=s+1;
r=r-1;
}
return true;
}
main(){
int n,t=1;
cin>>n ;        
n=n+1;
while(t){

if(palindrome(n)==true){
t=0;
}
else{
n++;
}
}
cout<<"Next No which is palindrome is = "<<n;
}


5. A sorted array has been rotated by some number k in clockwise direction. How can we  find k efficiently.
#include<iostream>
using namespace std;

int count(int arr[],int end){
int i=end;
while(end>=0){
if(arr[end]<arr[end-1]){
return end;
}
end--;
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n;               //size of array

for(i=0;i<n;i++){
cin>>arr[i];
}

int x =count(arr,n-1);
cout<<"\narray is rotated "<<x<<" times";

}

6. You are given with an array containing only 0’s and 1’s. Write a function to sort this  array. Find a solution which scans the array only once.

#include<iostream>
using namespace std;



void diffSort(int arr[], int startIndex, int endIndex){
int pindex=startIndex;
for(int i=startIndex;i<=endIndex;i++){
if(arr[i]==0){
swap(arr[pindex],arr[i]);
pindex++;
}
}
}


main(){
int n,arr[1000],i,j,k;
cin>>n;               //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}

}



 7. What if the array has 0’s, 1’s and 2’s. Find another solution which scans the array only  once. 

#include<iostream>
using namespace std;

int hash[1000];

void diffSort(int arr[], int startIndex, int endIndex){
for(int i=0;i<1000;i++){
hash[i]=0;
}

for(int i=startIndex;i<=endIndex;i++){
hash[arr[i]]=hash[arr[i]]++;
}
}


main(){
int n,arr[1000],i,j,k;
cin>>n;               //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<hash[0];i++){
arr[i]=0;
cout<<arr[i]<<"\t";
}
for(j=0;j<hash[1];j++){
arr[j+i]=1;
cout<<arr[j+i]<<"\t";
}
for(k=0;k<hash[2];k++){
arr[j+i+k]=2;
cout<<arr[j+i+k]<<"\t";
}
}



 8. Reverse a string keeping the words intact. e.g. Welcome to Coding Blocks ­> Blocks  Coding to Welcome.
9. Print all substrings of a string.
10.Print all subsequences of a String
11.Print all permutations of a String


12.Given an array find all subsets of A which sum to K.   

#include<iostream>
using namespace std;
void subset(int arr[],int temp[],int index,int subindex,int len,int sum){
if(index==len){

int t =0;

for(int i=0;i<=subindex;i++){
t=t+temp[i];
}
if(t==sum){
cout << "{ ";
for(int i=0;i<=subindex;i++){
cout << temp[i] << ", ";
}
cout<<" }\n";
}
return;
}
temp[subindex+1]=arr[index];
subset(arr,temp,index+1,subindex+1,len,sum);
subset(arr,temp,index+1,subindex,len,sum);
}



main(){
int n,sum;
int arr[100],temp[100];
cin >> n; //size of array
cin>>sum; //sum of subset
for (int i = 0; i < n ; i++) {
cin >> arr[i];
}

subset(arr,temp,0,-1,n,sum);

}