Re: [algogeeks] BST to DLL code: whats wrong with this code........
if u r getting desired output ? then what is the problem?
On Sun, Sep 2, 2012 at 7:24 PM, shubham jain coolshubham...@gmail.comwrote:
Hi
I am trying to convert the BST to doubly linked list but I am getting
desired output with this code Plz correct this code.
#includestdio.h
#includestdlib.h
typedef struct tree mytree;
struct tree
{
int data;
mytree* left;
mytree* right;
};
void insert(mytree** root,int data)
{
if(*root==NULL)
{
mytree* node=(mytree*)malloc(sizeof(mytree));
if(node==NULL)
return;
else
{
node-data=data;
node-left=NULL;
node-right=NULL;
}
*root=node;
return;
}
else
{
if((*root)-data =data)
insert((*root)-left,data);
else
insert((*root)-right,data);
}
}
void traverse(mytree* ptr)
{
if(ptr==NULL) return;
traverse(ptr-left);
printf(%d\t,ptr-data);
traverse(ptr-right);
}
void traversell(mytree* ptr)
{
if(ptr==NULL) return;
while(ptr!=NULL)
{
printf(%d\t,ptr-data);
ptr=ptr-right;
}
}
void bst22ll(mytree** tree,mytree** head)
{
static mytree* prev=NULL;
if(*tree==NULL) return;
mytree* ptr=*tree;
if((*tree)-left!=NULL)
bst22ll((*tree)-left,head);
*tree=ptr;
if(*head==NULL)
{
*head=*tree;
(*head)-left==NULL;
}
else
{
prev-right=*tree;
(*tree)-left=prev;
}
prev=*tree;
if((*tree)-right!=NULL)
{
bst22ll((*tree)-right,head);
}
}
void bst2ll(mytree** tree)
{
if(tree==NULL) return;
mytree* head=NULL;
mytree* prev=NULL;
bst22ll(tree,head);
*tree=head;
}
int main()
{
mytree* tree=NULL;
insert(tree,50);
insert(tree,40);
insert(tree,60);
insert(tree,30);
insert(tree,70);
insert(tree,65);
insert(tree,45);
insert(tree,34);
traverse(tree);
bst2ll(tree);
printf(\n);
traversell(tree);
printf(\n);
}
should print : 30 34 40 45 50 60 65 70
but printing: 30 34 40 45 50 60 70
Thank you
Shubham
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XXMvBSg0t08J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST to DLL code: whats wrong with this code........
Sorry by mistake i write that
Actually I am not getting desired output..
On Mon, Sep 3, 2012 at 11:02 AM, manish untwal manishuntw...@gmail.comwrote:
if u r getting desired output ? then what is the problem?
On Sun, Sep 2, 2012 at 7:24 PM, shubham jain coolshubham...@gmail.comwrote:
Hi
I am trying to convert the BST to doubly linked list but I am getting
desired output with this code Plz correct this code.
#includestdio.h
#includestdlib.h
typedef struct tree mytree;
struct tree
{
int data;
mytree* left;
mytree* right;
};
void insert(mytree** root,int data)
{
if(*root==NULL)
{
mytree* node=(mytree*)malloc(sizeof(mytree));
if(node==NULL)
return;
else
{
node-data=data;
node-left=NULL;
node-right=NULL;
}
*root=node;
return;
}
else
{
if((*root)-data =data)
insert((*root)-left,data);
else
insert((*root)-right,data);
}
}
void traverse(mytree* ptr)
{
if(ptr==NULL) return;
traverse(ptr-left);
printf(%d\t,ptr-data);
traverse(ptr-right);
}
void traversell(mytree* ptr)
{
if(ptr==NULL) return;
while(ptr!=NULL)
{
printf(%d\t,ptr-data);
ptr=ptr-right;
}
}
void bst22ll(mytree** tree,mytree** head)
{
static mytree* prev=NULL;
if(*tree==NULL) return;
mytree* ptr=*tree;
if((*tree)-left!=NULL)
bst22ll((*tree)-left,head);
*tree=ptr;
if(*head==NULL)
{
*head=*tree;
(*head)-left==NULL;
}
else
{
prev-right=*tree;
(*tree)-left=prev;
}
prev=*tree;
if((*tree)-right!=NULL)
{
bst22ll((*tree)-right,head);
}
}
void bst2ll(mytree** tree)
{
if(tree==NULL) return;
mytree* head=NULL;
mytree* prev=NULL;
bst22ll(tree,head);
*tree=head;
}
int main()
{
mytree* tree=NULL;
insert(tree,50);
insert(tree,40);
insert(tree,60);
insert(tree,30);
insert(tree,70);
insert(tree,65);
insert(tree,45);
insert(tree,34);
traverse(tree);
bst2ll(tree);
printf(\n);
traversell(tree);
printf(\n);
}
should print : 30 34 40 45 50 60 65 70
but printing: 30 34 40 45 50 60 70
Thank you
Shubham
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XXMvBSg0t08J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST question
correct me if I am wrong
#includestdio.h
struct node
{
int data;
struct node *left;
struct node * right;
}*root;
int sum(int s,struct node *p,int ar[],int l)
{
if(p == NULL )
{
return 0;
}
if(p-left == NULL p-right == NULL)
{
if( s - p-data == 0)
{
ar[l++] = p-data;
int i;
for( i = 0 ;i l ;i++)
{
printf(%d ,ar[i]);
}
printf(\n);
}
}
ar[l++] = p-data;
sum(s - p-data, p-left , ar , l);
sum(s - p-data, p-right , ar, l);
return 0;
}
struct node * getnode(int k)
{
struct node *temp = malloc(sizeof(struct node));
temp-data = k;
temp-left= NULL;
temp-right = NULL;
return temp;
}
main()
{
int ar[50],value;
root = getnode(5);
root-left= getnode(2);
root-right = getnode(2);
root-left-left = getnode(7);
root-left-right = getnode(8);
root-right-left = getnode(3);
root-right-right = getnode(7);
value = 14;
sum(value,root,ar,0);
return 0;
}
On Fri, Nov 11, 2011 at 12:38 PM, aniket chatterjee aniket...@gmail.comwrote:
Write a recursive function that will store each root to leaf path in an
array. Now for each root to leaf path find the subarray which sums up to X.
On Thu, Nov 10, 2011 at 11:53 PM, AMAN AGARWAL mnnit.a...@gmail.comwrote:
Hi All,
Please give me the solution of this problem.
A binary tree and a number X is given. Find all the paths(not necessarily
starting from root) such that the sum equals X.
Regards,
Aman.
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue that counts!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST question
As far as I understand, your solution will always contain the path that
essentially start from root. But the actual problem states that the path
may not necessarily start from root.
On Fri, Nov 11, 2011 at 1:21 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
correct me if I am wrong
#includestdio.h
struct node
{
int data;
struct node *left;
struct node * right;
}*root;
int sum(int s,struct node *p,int ar[],int l)
{
if(p == NULL )
{
return 0;
}
if(p-left == NULL p-right == NULL)
{
if( s - p-data == 0)
{
ar[l++] = p-data;
int i;
for( i = 0 ;i l ;i++)
{
printf(%d ,ar[i]);
}
printf(\n);
}
}
ar[l++] = p-data;
sum(s - p-data, p-left , ar , l);
sum(s - p-data, p-right , ar, l);
return 0;
}
struct node * getnode(int k)
{
struct node *temp = malloc(sizeof(struct node));
temp-data = k;
temp-left= NULL;
temp-right = NULL;
return temp;
}
main()
{
int ar[50],value;
root = getnode(5);
root-left= getnode(2);
root-right = getnode(2);
root-left-left = getnode(7);
root-left-right = getnode(8);
root-right-left = getnode(3);
root-right-right = getnode(7);
value = 14;
sum(value,root,ar,0);
return 0;
}
On Fri, Nov 11, 2011 at 12:38 PM, aniket chatterjee
aniket...@gmail.comwrote:
Write a recursive function that will store each root to leaf path in an
array. Now for each root to leaf path find the subarray which sums up to X.
On Thu, Nov 10, 2011 at 11:53 PM, AMAN AGARWAL mnnit.a...@gmail.comwrote:
Hi All,
Please give me the solution of this problem.
A binary tree and a number X is given. Find all the paths(not
necessarily starting from root) such that the sum equals X.
Regards,
Aman.
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue that counts!
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST question
And also your solution prints the root to leaf path that sums up to X. But
the path may not contain root as well as leaf also. May be some
intermediate 4 nodes (from root to leaf path)sums up to X. Your code doesnt
provide the solution for that scenario.
On Fri, Nov 11, 2011 at 2:53 PM, aniket chatterjee aniket...@gmail.comwrote:
As far as I understand, your solution will always contain the path that
essentially start from root. But the actual problem states that the path
may not necessarily start from root.
On Fri, Nov 11, 2011 at 1:21 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.com wrote:
correct me if I am wrong
#includestdio.h
struct node
{
int data;
struct node *left;
struct node * right;
}*root;
int sum(int s,struct node *p,int ar[],int l)
{
if(p == NULL )
{
return 0;
}
if(p-left == NULL p-right == NULL)
{
if( s - p-data == 0)
{
ar[l++] = p-data;
int i;
for( i = 0 ;i l ;i++)
{
printf(%d ,ar[i]);
}
printf(\n);
}
}
ar[l++] = p-data;
sum(s - p-data, p-left , ar , l);
sum(s - p-data, p-right , ar, l);
return 0;
}
struct node * getnode(int k)
{
struct node *temp = malloc(sizeof(struct node));
temp-data = k;
temp-left= NULL;
temp-right = NULL;
return temp;
}
main()
{
int ar[50],value;
root = getnode(5);
root-left= getnode(2);
root-right = getnode(2);
root-left-left = getnode(7);
root-left-right = getnode(8);
root-right-left = getnode(3);
root-right-right = getnode(7);
value = 14;
sum(value,root,ar,0);
return 0;
}
On Fri, Nov 11, 2011 at 12:38 PM, aniket chatterjee
aniket...@gmail.comwrote:
Write a recursive function that will store each root to leaf path in an
array. Now for each root to leaf path find the subarray which sums up to X.
On Thu, Nov 10, 2011 at 11:53 PM, AMAN AGARWAL mnnit.a...@gmail.comwrote:
Hi All,
Please give me the solution of this problem.
A binary tree and a number X is given. Find all the paths(not
necessarily starting from root) such that the sum equals X.
Regards,
Aman.
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue that counts!
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST question
Write a recursive function that will store each root to leaf path in an array. Now for each root to leaf path find the subarray which sums up to X. On Thu, Nov 10, 2011 at 11:53 PM, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi All, Please give me the solution of this problem. A binary tree and a number X is given. Find all the paths(not necessarily starting from root) such that the sum equals X. Regards, Aman. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
Do a BFS of the tree, keep a separator to masrk where a level ends.. create the linklist for every level. On Wed, Sep 21, 2011 at 6:00 PM, prasanth n nprasnt...@gmail.com wrote: Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists). -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
take countr to be a static variable ... that shud do the job ...!! btw ...if thats nt the case ... thn i m nt pretty sure wat u are asking to be done ... On Sun, Jul 31, 2011 at 2:12 AM, Rahul Mittal rahulmitta...@gmail.comwrote: help me with this we need to find out how many times a function is recursively called while inserting a node in bst. insert (number X, node N) increase the counter C by 1 if X is less than the number in node N if N has no left child create a new node with the number X and set it to be the left child of node N else insert (X, left child of node N) else (X is greater than the number in node N) if N has no right child create a new node with the number X and set it to be the right child of node N else insert (X, right child of node N) we need value of count PS:this algorithm will exceed time limit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
please give an example. On Sat, Jul 30, 2011 at 12:10 PM, Mani Bharathi manibharat...@gmail.comwrote: connect all sibling nodes of a binary search tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/GWAhIi6vaxAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
Do u mean something like level order traversal?? On Sat, Jul 30, 2011 at 12:11 PM, saurabh singh saurab...@gmail.com wrote: please give an example. On Sat, Jul 30, 2011 at 12:10 PM, Mani Bharathi manibharat...@gmail.comwrote: connect all sibling nodes of a binary search tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/GWAhIi6vaxAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
http://mukeshiiitm.wordpress.com/2010/04/07/finding-kth-smallest-element-in-binary/ I think this solves the problem :) Rajeev On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal mittal.nishan...@gmail.comwrote: how to find kth smallest element in BST... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
At each node if we store the Number of nodes in the left subtree.we can find kth smallest in O(lgn) else do a inorder traversal for k nodes On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal mittal.nishan...@gmail.comwrote: how to find kth smallest element in BST... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
Order Statistics Tree On Wed, Jun 29, 2011 at 8:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: At each node if we store the Number of nodes in the left subtree.we can find kth smallest in O(lgn) else do a inorder traversal for k nodes On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal mittal.nishan...@gmail.com wrote: how to find kth smallest element in BST... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Regards,* *Piyush Kapoor,* *CSE-IT-BHU* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
This should be very simple... follow inorder..
Inorder(Node* node, int counter, int N)
{
if(node == null)return;
Inorder(node-left, counter, N);
counter++;
if(counter == N)
{
print(node-data);
return;
}
Inorder(node-right, counter, N);
}
On Wed, Jun 29, 2011 at 9:03 PM, piyush kapoor pkjee2...@gmail.com wrote:
Order Statistics Tree
On Wed, Jun 29, 2011 at 8:15 PM, sunny agrawal sunny816.i...@gmail.comwrote:
At each node if we store the Number of nodes in the left subtree.we
can find kth smallest in O(lgn)
else do a inorder traversal for k nodes
On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal
mittal.nishan...@gmail.com wrote:
how to find kth smallest element in BST...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Regards,*
*Piyush Kapoor,*
*CSE-IT-BHU*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
Check this
http://ideone.com/o8gF2
On Wed, Jun 29, 2011 at 10:28 PM, Swathi chukka.swa...@gmail.com wrote:
This should be very simple... follow inorder..
Inorder(Node* node, int counter, int N)
{
if(node == null)return;
Inorder(node-left, counter, N);
counter++;
if(counter == N)
{
print(node-data);
return;
}
Inorder(node-right, counter, N);
}
On Wed, Jun 29, 2011 at 9:03 PM, piyush kapoor pkjee2...@gmail.comwrote:
Order Statistics Tree
On Wed, Jun 29, 2011 at 8:15 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
At each node if we store the Number of nodes in the left subtree.we
can find kth smallest in O(lgn)
else do a inorder traversal for k nodes
On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal
mittal.nishan...@gmail.com wrote:
how to find kth smallest element in BST...
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Regards,*
*Piyush Kapoor,*
*CSE-IT-BHU*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.comwrote: then you can use iterative method instead of recursion ... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
traverse the BST , get the count of no. of nodes . now inorder traverse again till n/2 . and print that node On Sat, Jun 18, 2011 at 11:18 PM, Akshata Sharma akshatasharm...@gmail.com wrote: How to find median of a Binary Search Tree without storing it in a linear data structure by in-order traversal? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
if no recursion and extra space is allowed?? On Sat, Jun 18, 2011 at 11:20 PM, Vipul Kumar vipul.k.r...@gmail.comwrote: traverse the BST , get the count of no. of nodes . now inorder traverse again till n/2 . and print that node On Sat, Jun 18, 2011 at 11:18 PM, Akshata Sharma akshatasharm...@gmail.com wrote: How to find median of a Binary Search Tree without storing it in a linear data structure by in-order traversal? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
then you can use iterative method instead of recursion ... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
oh ya thanks now i got it On Sun, Oct 24, 2010 at 9:54 AM, preetika tyagi preetikaty...@gmail.comwrote: @Praveen- In this case, we will not ignore the right subtree of the root (-10, which is less than zero) while traversing the tree. On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar praveen200...@gmail.comwrote: i think it is possible nishaanth please do take a look at this example -10 /\ -11 8 /\ -5 10 -5 is greater than -10 On Sat, Oct 23, 2010 at 11:19 PM, nishaanth nishaant...@gmail.comwrote: @Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.com wrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.comwrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
@Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.comwrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.com wrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
i think it is possible nishaanth please do take a look at this example -10 /\ -11 8 /\ -5 10 -5 is greater than -10 On Sat, Oct 23, 2010 at 11:19 PM, nishaanth nishaant...@gmail.com wrote: @Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.comwrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.comwrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
@Praveen- In this case, we will not ignore the right subtree of the root (-10, which is less than zero) while traversing the tree. On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar praveen200...@gmail.comwrote: i think it is possible nishaanth please do take a look at this example -10 /\ -11 8 /\ -5 10 -5 is greater than -10 On Sat, Oct 23, 2010 at 11:19 PM, nishaanth nishaant...@gmail.com wrote: @Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.comwrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.comwrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
@nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.com wrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
4th element of inorder traversal On Fri, Oct 8, 2010 at 11:49 PM, Anand anandut2...@gmail.com wrote: Binary search Tree was given. Find 4ths smallest element. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Problem
@priyanka i agree with u... but wat i thot was if v had a tree with parent pointers...we can have one pointer at the left most and another at the rightmost subtree respectivelyand move along the pointers.. I need ur discussion on thisi think the implementation wud be difficult..converting it to a DLL is quite elegant.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST sort
u need to write a recursive function. All leaf nodes in complete BST are from n/2+1n. n/2+1 element will be the beginning element(least left child) for our resultant sorted array. U can get the parent of the element by doing the floor(n/2/+1), get the right child of the parent by 2*(floor(n/2/+1))+1, do it recursively for its parent and so ... on till the parent index is 0 . Satya On Fri, Aug 6, 2010 at 3:37 PM, sharad kumar aryansmit3...@gmail.comwrote: perform inorder traversal...and store it in same array... On Thu, Aug 5, 2010 at 7:10 PM, AlgoBoy manjunath.n...@gmail.com wrote: sort a BST represented like an array...(similar to representation of HEAP) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST sort
typo! floor(n/2/+1) == floor((n/2/+1)/2) . Satya On Fri, Aug 6, 2010 at 5:27 PM, Satya satya...@gmail.com wrote: u need to write a recursive function. All leaf nodes in complete BST are from n/2+1n. n/2+1 element will be the beginning element(least left child) for our resultant sorted array. U can get the parent of the element by doing the floor(n/2/+1), get the right child of the parent by 2*(floor(n/2/+1))+1, do it recursively for its parent and so ... on till the parent index is 0 . Satya On Fri, Aug 6, 2010 at 3:37 PM, sharad kumar aryansmit3...@gmail.comwrote: perform inorder traversal...and store it in same array... On Thu, Aug 5, 2010 at 7:10 PM, AlgoBoy manjunath.n...@gmail.com wrote: sort a BST represented like an array...(similar to representation of HEAP) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Problem
@algoboy: If you want to use extra space go with sharad's algo: do inorder traversal , store in a buffer and use 2 pointer method. T(n) =O(n) , S(n)=O(n) If you don't want to use extra space , convert BST into circular DLL or DLL and use 2 pointer algorithm. (conversion of BST into DLL is a simple algo, already discussed) T(n)=O(n) , S(n) =O(1). The only problem is you change the structure . (There probably exists a working algo to convert a DLL to BST , i haven't tried that yet although) -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST with duplicates?
Disagree a BST can have duplicate entries the 'equal to' term in the definition allows that I am surprised to see in the Wiki: From the above properties it naturally follows that: - Each node (item in the tree) has a distinct key. The example in the question is definitely wrong in the sense that it allows duplicates in both directions once the definition is fixed one can have duplicates in 1 direction i.e. left or right I believe. On Thu, Jul 1, 2010 at 10:01 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Amit as per wiki, BST definition is - The left subtree of a node contains only nodes with keys *less than the node's key*. - The right subtree of a node contains only nodes with *keys greater than or equal to the node's key*. so, this following example is not a BST... Mohit On Thu, Jul 1, 2010 at 8:04 PM, amit amitjaspal...@gmail.com wrote: Can a BST have duplicate entries ?? .8 .../...\ .7..9 /..\/..\ ...6...8..8...10 i.e is this a BST . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST with duplicates?
no a bst cant hve duplicates -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST with duplicates?
@Amit as per wiki, BST definition is - The left subtree of a node contains only nodes with keys *less than the node's key*. - The right subtree of a node contains only nodes with *keys greater than or equal to the node's key*. so, this following example is not a BST... Mohit On Thu, Jul 1, 2010 at 8:04 PM, amit amitjaspal...@gmail.com wrote: Can a BST have duplicate entries ?? .8 .../...\ .7..9 /..\/..\ ...6...8..8...10 i.e is this a BST . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
I think in-order traversal would solve the problem. On Thu, Jun 24, 2010 at 4:24 PM, Anurag Sharma anuragvic...@gmail.comwrote: I once posted it to my blog. Perhaps its the same you are asking : http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html Anurag Sharma On Mon, Jun 21, 2010 at 1:55 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: CAN ANY 1 GIVE THE ALGORITHM.. HOW TO CONVERT BST TO dLL -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks, Chakravarthi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST...doubt.......
@sharad height will be log2(n) only in case of balanced BST. what if its terribly unbalanced, you may get height as 'n' as well ! :) So you will have to go till the bottom of the tree to see the depth and find the height accordingly. Anurag Sharma On Wed, Jun 16, 2010 at 9:12 AM, Anurag Sharma anuragvic...@gmail.comwrote: height of current node = max(height of left child, height of right child) +1 Hope now you get that? :) Anurag Sharma On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar ajaykr@gmail.com wrote: Write a pseudo code 4 that..using c/c++... how can we find the depth(height) of BST ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST...doubt.......
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max( depth( n.right ) , depth( n.left ) );
}
calling depth(root) will yield the height of the tree
On 6/15/10, ajay kumar ajaykr@gmail.com wrote:
Write a pseudo code 4 that..using c/c++...
how can we find the depth(height) of BST ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST...doubt.......
@ajay:recursively count the number of nodes then use formula h=log2(number
of nodes)
On Wed, Jun 16, 2010 at 5:39 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max( depth( n.right ) , depth( n.left ) );
}
calling depth(root) will yield the height of the tree
On 6/15/10, ajay kumar ajaykr@gmail.com wrote:
Write a pseudo code 4 that..using c/c++...
how can we find the depth(height) of BST ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST...doubt.......
height of current node = max(height of left child, height of right child) +1 Hope now you get that? :) Anurag Sharma On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar ajaykr@gmail.com wrote: Write a pseudo code 4 that..using c/c++... how can we find the depth(height) of BST ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
form a sorted array from inorder traversal of tree. now take to pointers one to the beginning of array and other at the end. now check if the sum of element is greater than reqd sum then increment 1st ptr. if their sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd sum then this is the ans.. hope it will work.. On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: given a bst... find two nodes whose sum is equal to a number k ... in O(n) time and constant space... -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
use a hash table.
Add the frst element in the hash table.
From second element, check if the diff (sum - element) is present in the
hash table or not.
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we should
start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s= x
+ y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to pointers
one to the beginning of array and other at the end. now check if the sum of
element is greater than reqd sum then increment 1st ptr. if their sum is
less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd
sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
- NMN
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum req sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum 6)
dec ptr2 1+4 = 5 (sum 6)
inc ptr2: 2+4 =6 (got the ans)
But the qs mentions that it should be in O(1) space.
Regards,
Anna
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we should
start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s= x
+ y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to pointers
one to the beginning of array and other at the end. now check if the sum of
element is greater than reqd sum then increment 1st ptr. if their sum is
less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd
sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST
hmmm i already realised that and even mailed that before :)
and if we want to use constant space do not make an array. the bst
itself is good enough to do what we are doing.
On 5/14/10, anna thomas annathoma...@gmail.com wrote:
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum req sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum 6)
dec ptr2 1+4 = 5 (sum 6)
inc ptr2: 2+4 =6 (got the ans)
But the qs mentions that it should be in O(1) space.
Regards,
Anna
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we
should
start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K
prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s=
x
+ y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain
sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to
pointers
one to the beginning of array and other at the end. now check if the sum
of
element is greater than reqd sum then increment 1st ptr. if their sum is
less than reqd sum then decrement 2nd ptr. if their sum is equal to the
reqd
sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
Re: [algogeeks] BST
if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)
have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..
On Fri, May 14, 2010 at 5:03 PM, anna thomas annathoma...@gmail.com wrote:
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum req sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum 6)
dec ptr2 1+4 = 5 (sum 6)
inc ptr2: 2+4 =6 (got the ans)
But the qs mentions that it should be in O(1) space.
Regards,
Anna
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries sum, we
should start with the smallest element
and scan the elements from last till we get some value x which together
with the smallest value sums to sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 3:51 PM, Prashant K prashant.r.k...@gmail.comwrote:
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - ith number (node)
3) now search for 'y' in BST if we found then there is node such that s=
x + y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana Sukhino Bhavanthu ||
On Fri, May 14, 2010 at 2:47 AM, divya jain sweetdivya@gmail.comwrote:
form a sorted array from inorder traversal of tree. now take to
pointers one to the beginning of array and other at the end. now check if
the sum of element is greater than reqd sum then increment 1st ptr. if
their
sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to
the reqd sum then this is the ans..
hope it will work..
On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a bst... find two nodes whose sum is equal to a number k ... in
O(n) time and constant space...
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
