Hector
BAN USER#include<conio.h>
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node*left;
struct node*right;
};
void insert(struct node**q,int num)
{
struct node *temp=NULL;
temp=(struct node*)malloc(sizeof(struct node));
if(*q==NULL)
{
temp->data=num;
temp->left=NULL;
temp->right=NULL;
*q=temp;
// printf("%d\n",temp->data);
}
else
{
if(((*q)->data)>num)
insert(&((*q)->left),num);
else
insert(&((*q)->right),num);
}
}
void trim(struct node**p,int m,int n)
{
struct node*temp=*p;
if(*p==NULL)
return;
else
{
if(m>(*p)->data)
{
*p=(*p)->right;
temp->left=NULL;
temp->right=NULL;
free(temp);
trim(p,m,n);
}
else
{
if(n<(*p)->data)
{
*p=(*p)->left;
temp->left=NULL;
temp->right=NULL;
free(temp);
trim(p,m,n);;
}
else
{
trim(&(*p)->left,m,(*p)->data);
trim(&(*p)->right,(*p)->data,n);
}
}
}
}
void inorder(struct node*z)
{
if(z!=NULL)
{
inorder(z->left);
printf("%d\t",z->data);
inorder(z->right);
}
else return;
}
int main()
{
struct node*p;
p=NULL;
insert(&p,17);
insert(&p,13);
insert(&p,21);
insert(&p,27);
insert(&p,19);
insert(&p,8);
insert(&p,15);
trim(&p,20,25);
inorder(p);
getch();
return 0;
}
Did i speak insane??
- Hector August 21, 2013First of all sort it in nlogn so without using extra space.
Now all neagtive numebrs are in starting and +ve are at end.
So keep two pointers one in starting and one at end and start swapping the numbers in o(n) till both pointers meet.